2026-07-24T12:54:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11177 2024-03-06T10:47:38Z ddc:004 open_access

Towards Improving Christofides Algorithm for Half-Integer TSP Haddadan, Arash Newman, Alantha Traveling salesman problem subtour elimination relaxation integrality gap gluing subtours We study the traveling salesman problem (TSP) in the case when the objective function of the subtour linear programming relaxation is minimized by a half-cycle point: x_e in {0,1/2,1} where the half-edges form a 2-factor and the 1-edges form a perfect matching. Such points are sufficient to resolve half-integer TSP in general and they have been conjectured to demonstrate the largest integrality gap for the subtour relaxation. For half-cycle points, the best-known approximation guarantee is 3/2 due to Christofides' famous algorithm. Proving an integrality gap of alpha for the subtour relaxation is equivalent to showing that alpha x can be written as a convex combination of tours, where x is any feasible solution for this relaxation. To beat Christofides' bound, our goal is to show that (3/2 - epsilon)x can be written as a convex combination of tours for some positive constant epsilon. Let y_e = 3/2-epsilon when x_e = 1 and y_e = 3/4 when x_e = 1/2. As a first step towards this goal, our main result is to show that y can be written as a convex combination of tours. In other words, we show that we can save on 1-edges, which has several applications. Among them, it gives an alternative algorithm for the recently studied uniform cover problem. Our main new technique is a procedure to glue tours over proper 3-edge cuts that are tight with respect to x, thus reducing the problem to a base case in which such cuts do not occur. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arash Haddadan and Alantha Newman 2019 Is Part Of LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2019.56 urn:nbn:de:0030-drops-111772 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.56 eng https://creativecommons.org/licenses/by/3.0/legalcode