Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes

DOI10.1016/J.DISOPT.2021.100659MaRDI QIDQ2067494zbMATH OpenOpenAlexFDO

Authors Arash Haddadan, Alantha Newman

Publication date 18 January 2022

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.09906

zbMATH Keywords

convex combinationintegrality gap2-edge-connected multigraph

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Finding the exact integrality gap $alpha$ for the LP relaxation of the 2-edge-connected spanning multigraph problem (2EC) is closely related to the same problem for the Held-Karp relaxation of the metric traveling salesman problem (TSP). While the former problem seems easier than the latter, since it is less constrained, currently the upper bounds on the respective integrality gaps for the two problems are the same. An approach to proving integrality gaps for both of these problems is to consider fundamental classes of extreme points. For 2EC, better bounds on the integrality gap are known for certain important special cases of these fundamental points. For example, for half-integer square points, the integrality gap is between $frac65$ and $frac43$. Our main result is to improve the approximation factor to $frac97$ for 2EC for these points. Our approach is based on constructing convex combinations and our key tool is the top-down coloring framework for tree augmentation, whose flexibility we employ to exploit beneficial properties in both the initial spanning tree and in the input graph. We also show how these tools can be tailored to the closely related problem of uniform covers for which the proofs of the best-known bounds do not yield polynomial-time algorithms. Another key ingredient is to use a rainbow spanning tree decomposition, which allows us to obtain a convex combination of spanning trees with particular properties

Recommendations

• Toward a 6/5 bound for the minimum cost 2-edge connected subgraph problem
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations
• scientific article; zbMATH DE number 1187146

Cites work

• scientific article; zbMATH DE number 1187146 (Why is no real title available?)
• scientific article; zbMATH DE number 1405806 (Why is no real title available?)
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case
• A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs
• A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Connectivity of orientations of 3-edge-connected graphs
• Edge-Disjoint Spanning Trees of Finite Graphs
• Finding 2-factors closer to TSP tours in cubic graphs
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Heuristic analysis, linear programming and branch and bound
• Matchings in regular graphs
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Shorter tours and longer detours: uniform covers and a bit beyond
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
• Spanning trees with many or few colors in edge-colored graphs
• The salesman's improved tours for fundamental classes
• Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
• Unions of perfect matchings in cubic graphs
• Worst-case comparison of valid inequalities for the TSP

Cited in

(5)

• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• scientific article; zbMATH DE number 7525493 (Why is no real title available?)
• A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case
• Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours
• Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs

This page was built for publication: Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2067494)