arXiv preprint ·
Approximating graphic TSP by b-matchings
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We give a polynomial-time algorithm for graphic TSP that returns a tour of length at most $\frac{89}{64}=\frac{7}{5}-\frac{3}{320}$ times the value of the subtour relaxation. This improves the long-standing ratio $\frac75$ of Sebő and Vygen and shows that the integrality gap of the subtour LP on graphic instances is at most $\frac{89}{64}\approx 1.3906$. We optimize a non-linear objective function over an odd-join polytope, which uses (i) a new removable system of edges, and (ii) reconnection of subtours if the graph is disconnected. This approach gives a $\frac{13}{10}$-approximation algorithm for $4$-regular $4$-vertex-connected graphs, improving the $\frac43$ of Newman, and a $\frac43$-approximation for $k$-vertex-connected graphs of maximum degree at most $k+1$, for every $k\ge 3$. For the general graphic TSP, we construct a feasible point in the odd-join polytope, using an optimal vertex from the Subtour linear programming relaxation of TSP, which helps us bound the approximation factor by 89/64.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Greedy+Singleton for knapsack-constrained monotone submodular maximization has approximation ratio exactly $β^\star \approx 0.42944$
Explicit Subspace Evasive Sets via Subspace Designs
Small classes have linear neighbourhood complexity
Rotating Walks, Derandomized Squares, and Permutation Conjugated Walks
Integrality Gap of 3.4 for Santa Claus: A Topology-based Analysis
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.