Shorter tours and longer detours: uniform covers and a bit beyond
From MaRDI portal
Publication:2220659
DOI10.1007/s10107-019-01426-8zbMath1458.90546arXiv1707.05387OpenAlexW2969350440WikidataQ127372383 ScholiaQ127372383MaRDI QIDQ2220659
R. Ravi, Alantha Newman, Arash Haddadan
Publication date: 25 January 2021
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.05387
Related Items (5)
A deterministic better-than-3/2 approximation algorithm for metric TSP ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Unnamed Item ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes ⋮ Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Minimum-weight two-connected spanning networks
- Survivable networks, linear programming relaxations and the parsimonious property
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Analyzing the Held-Karp TSP bound: A monotonicity property with application
- On the integrality ratio for tree augmentation
- On the relationship between the biconnectivity augmentation and traveling salesman problems
- Geometric algorithms and combinatorial optimization
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
- Worst-case comparison of valid inequalities for the TSP
- \(\frac{13}{9}\)-approximation for graphic TSP
- The saleman's improved tours for fundamental classes
- The traveling salesman problem on cubic and subcubic graphs
- Finding 2-Factors Closer to TSP Tours in Cubic Graphs
- Removing and Adding Edges for the Traveling Salesman Problem
- Cycles Intersecting Edge-Cuts of Prescribed Sizes
- Heuristic analysis, linear programming and branch and bound
- Approximation Algorithms for Several Graph Augmentation Problems
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Matching, Euler tours and the Chinese postman
- Toward a 6/5 Bound for the Minimum Cost 2-Edge Connected Spanning Subgraph
- A Randomized Rounding Approach to the Traveling Salesman Problem
This page was built for publication: Shorter tours and longer detours: uniform covers and a bit beyond
