IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v39y2020i4d10.1007_s10878-020-00535-x.html
   My bibliography  Save this article

Co-density and fractional edge cover packing

Author

Listed:
  • Qiulan Zhao

    (Nanjing University)

  • Zhibin Chen

    (Kunming University of Science and Technology)

  • Jiajun Sang

    (The University of Hong Kong)

Abstract

Given a multigraph $$G=(V,E)$$G=(V,E), the edge cover packing problem (ECPP) on G is to find a coloring of edges of G using the maximum number of colors such that at each vertex all colors occur. ECPP can be formulated as an integer program and is NP-hard in general. In this paper, we consider the fractional edge cover packing problem, the LP relaxation of ECPP. We focus on the more general weighted setting, the weighted fractional edge cover packing problem (WFECPP), which can be formulated as the following linear program $$\begin{aligned} \begin{array}{ll} \hbox {Maximize} \ \ \ &{} {{\varvec{1}}}^T {{\varvec{x}}} \\ \hbox {subject to} &{} A{{\varvec{x}}} \le {{\varvec{w}}} \\ &{} \quad {{\varvec{x}}} \ge {{\varvec{0}}}, \end{array} \end{aligned}$$Maximize1Txsubject toAx≤wx≥0,where A is the edge–edge cover incidence matrix of G, $${\varvec{w}}=(w(e): e\in E)$$w=(w(e):e∈E), and w(e) is a positive rational weight on each edge e of G. The weighted co-density problem, closely related to WFECPP, is to find a subset $$S\subseteq V$$S⊆V with $$|S|\ge 3$$|S|≥3 and odd, such that $$\frac{2w(E^{+}(S))}{|S|+1}$$2w(E+(S))|S|+1 is minimized, where $$E^{+}(S)$$E+(S) is the set of all edges of G with at least one end in S and $$w(E^{+}(S))$$w(E+(S)) is the total weight of all edges in $$E^{+}(S)$$E+(S). We present polynomial combinatorial algorithms for solving these two problems exactly.

Suggested Citation

  • Qiulan Zhao & Zhibin Chen & Jiajun Sang, 2020. "Co-density and fractional edge cover packing," Journal of Combinatorial Optimization, Springer, vol. 39(4), pages 955-987, May.
  • Handle: RePEc:spr:jcomop:v:39:y:2020:i:4:d:10.1007_s10878-020-00535-x
    DOI: 10.1007/s10878-020-00535-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00535-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.

    File URL: https://libkey.io/10.1007/s10878-020-00535-x?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Manfred W. Padberg & M. R. Rao, 1982. "Odd Minimum Cut-Sets and b -Matchings," Mathematics of Operations Research, INFORMS, vol. 7(1), pages 67-80, February.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Lisa K. Fleischer & Adam N. Letchford & Andrea Lodi, 2006. "Polynomial-Time Separation of a Superclass of Simple Comb Inequalities," Mathematics of Operations Research, INFORMS, vol. 31(4), pages 696-713, November.
    2. Fan Zhang, 2003. "A Separation Algorithm for b -Matching Degree-Sequence Polyhedra," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 92-102, February.
    3. Barbara De Rosa & Gennaro Improta & Gianpaolo Ghiani & Roberto Musmanno, 2002. "The Arc Routing and Scheduling Problem with Transshipment," Transportation Science, INFORMS, vol. 36(3), pages 301-313, August.
    4. Julián Aráoz & Elena Fernández & Carles Franquesa, 2017. "The Generalized Arc Routing Problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 25(3), pages 497-525, October.
    5. Salazar-González, Juan-José, 2021. "Designing optimal masks for a multi-object spectrometer," Omega, Elsevier, vol. 103(C).
    6. Michele Conforti & Gérard Cornuéjols & Giacomo Zambelli, 2013. "Extended formulations in combinatorial optimization," Annals of Operations Research, Springer, vol. 204(1), pages 97-143, April.
    7. Quoc Trung Bui & Yves Deville & Quang Dung Pham, 2016. "Exact methods for solving the elementary shortest and longest path problems," Annals of Operations Research, Springer, vol. 244(2), pages 313-348, September.
    8. Luc Muyldermans & Patrick Beullens & Dirk Cattrysse & Dirk Van Oudheusden, 2005. "Exploring Variants of 2-Opt and 3-Opt for the General Routing Problem," Operations Research, INFORMS, vol. 53(6), pages 982-995, December.
    9. Manfred Padberg, 2005. "Classical Cuts for Mixed-Integer Programming and Branch-and-Cut," Annals of Operations Research, Springer, vol. 139(1), pages 321-352, October.
    10. A N Letchford & J Lysgaard & R W Eglese, 2007. "A branch-and-cut algorithm for the capacitated open vehicle routing problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(12), pages 1642-1651, December.
    11. Neamatian Monemi, Rahimeh & Gelareh, Shahin & Nagih, Anass & Maculan, Nelson & Danach, Kassem, 2021. "Multi-period hub location problem with serial demands: A case study of humanitarian aids distribution in Lebanon," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    12. Caterina De Simone & Anna Galluccio, 2009. "Edge-colouring of joins of regular graphs, I," Journal of Combinatorial Optimization, Springer, vol. 18(4), pages 417-428, November.
    13. Robert Carr, 2004. "Separation Algorithms for Classes of STSP Inequalities Arising from a New STSP Relaxation," Mathematics of Operations Research, INFORMS, vol. 29(1), pages 80-91, February.
    14. Orlis, Christos & Laganá, Demetrio & Dullaert, Wout & Vigo, Daniele, 2020. "Distribution with Quality of Service Considerations: The Capacitated Routing Problem with Profits and Service Level Requirements," Omega, Elsevier, vol. 93(C).
    15. William Cook & Daniel G. Espinoza & Marcos Goycoolea, 2007. "Computing with Domino-Parity Inequalities for the Traveling Salesman Problem (TSP)," INFORMS Journal on Computing, INFORMS, vol. 19(3), pages 356-365, August.
    16. Karthekeyan Chandrasekaran & László A. Végh & Santosh S. Vempala, 2016. "The Cutting Plane Method is Polynomial for Perfect Matchings," Mathematics of Operations Research, INFORMS, vol. 41(1), pages 23-48, February.
    17. Zang, Xiaoning & Jiang, Li & Liang, Changyong & Fang, Xiang, 2023. "Coordinated home and locker deliveries: An exact approach for the urban delivery problem with conflicting time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).
    18. Elena Fernández & Oscar Meza & Robert Garfinkel & Maruja Ortega, 2003. "On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation," Operations Research, INFORMS, vol. 51(2), pages 281-291, April.
    19. Ruizhi Lin & Heping Zhang, 2020. "Fractional matching preclusion number of graphs and the perfect matching polytope," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 915-932, April.
    20. Gilbert Laporte & Jorge Riera-Ledesma & Juan-José Salazar-González, 2003. "A Branch-and-Cut Algorithm for the Undirected Traveling Purchaser Problem," Operations Research, INFORMS, vol. 51(6), pages 940-951, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:39:y:2020:i:4:d:10.1007_s10878-020-00535-x. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.