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

DOI10.1016/J.DISOPT.2021.100659zbMATH Open1506.90258arXiv1811.09906OpenAlexW2920960746MaRDI QIDQ2067494FDOQ2067494

Arash Haddadan, Alantha Newman

Publication date: 18 January 2022

Published in: Discrete Optimization (Search for Journal in Brave)

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

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

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 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)

Cites Work

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

Cited In (5)

• Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
• Title not available (Why is that?)
• 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)