Abstract
We study the traveling salesman problem (TSP) in the case when the objective function of the subtour linear programming relaxation is minimized by a halfcycle point: x_e in {0,1/2,1} where the halfedges form a 2factor and the 1edges form a perfect matching. Such points are sufficient to resolve halfinteger TSP in general and they have been conjectured to demonstrate the largest integrality gap for the subtour relaxation.
For halfcycle points, the bestknown 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/2epsilon 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 1edges, 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 3edge cuts that are tight with respect to x, thus reducing the problem to a base case in which such cuts do not occur.
BibTeX  Entry
@InProceedings{haddadan_et_al:LIPIcs:2019:11177,
author = {Arash Haddadan and Alantha Newman},
title = {{Towards Improving Christofides Algorithm for HalfInteger TSP}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {56:156:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11177},
URN = {urn:nbn:de:0030drops111772},
doi = {10.4230/LIPIcs.ESA.2019.56},
annote = {Keywords: Traveling salesman problem, subtour elimination relaxation, integrality gap, gluing subtours}
}
Keywords: 

Traveling salesman problem, subtour elimination relaxation, integrality gap, gluing subtours 
Collection: 

27th Annual European Symposium on Algorithms (ESA 2019) 
Issue Date: 

2019 
Date of publication: 

06.09.2019 