Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours

DOI10.1007/s10107-022-01784-wOpenAlexW3033262378MaRDI QIDQ2687058

Publication date: 1 March 2023

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
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
On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
Worst-case comparison of valid inequalities for the TSP
Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes
Shorter tours and longer detours: uniform covers and a bit beyond
The salesman's improved tours for fundamental classes
On the approximability of the traveling salesman problem
Finding 2-Factors Closer to TSP Tours in Cubic Graphs
The Design of Approximation Algorithms
Removing and Adding Edges for the Traveling Salesman Problem
Integer Programming
The traveling salesman problem in graphs with 3-edge cutsets
Heuristic analysis, linear programming and branch and bound
Spanning trees with many or few colors in edge-colored graphs
Halin graphs and the travelling salesman problem
Matching, Euler tours and the Chinese postman
An improved approximation algorithm for TSP in the half integral case
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
A Randomized Rounding Approach to the Traveling Salesman Problem
A (slightly) improved approximation algorithm for metric TSP

This page was built for publication: Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours