Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
From MaRDI portal
Publication:2067494
DOI10.1016/j.disopt.2021.100659zbMath1506.90258arXiv1811.09906OpenAlexW2920960746MaRDI QIDQ2067494
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
Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items (5)
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 ⋮ Unnamed Item ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
Cites Work
- 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
- Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
- 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
- Matchings in regular graphs
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- Worst-case comparison of valid inequalities for the TSP
- Shorter tours and longer detours: uniform covers and a bit beyond
- The salesman's improved tours for fundamental classes
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- Connectivity of orientations of 3-edge-connected graphs
- Finding 2-Factors Closer to TSP Tours in Cubic Graphs
- Edge-Disjoint Spanning Trees of Finite Graphs
- Unions of perfect matchings in cubic graphs
- Heuristic analysis, linear programming and branch and bound
- Spanning trees with many or few colors in edge-colored graphs
- 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
- Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
- An O(log n/log log n)-Approximation Algorithm for the Asymmetric Traveling Salesman Problem
- [https://portal.mardi4nfdi.de/wiki/Publication:6058192 A $4/3$-Approximation Algorithm for the Minimum $2$-Edge Connected Multisubgraph Problem in the Half-Integral Case]
- Unnamed Item
- Unnamed Item
This page was built for publication: Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
