Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem

Robert D. Carr, Santosh Vempala

Abstract

A long-standing conjecture in combinatorial optimization says that the integrality gap of the famous Held-Karp relaxation of the symmetric TSP is precisely 4/3. In this paper, we show that a slight strengthening of this conjecture implies a tight 4/3 integrality gap for a linear programming relaxation of the asymmetric TSP. This is surprising since no constant-factor approximation is known for the latter problem. Our main tools are a new characterization of the integrality gap for linear objective functions over polyhedra, and the isolation of ''hard-to-round'' solutions of the relaxations.
BibTeX
@inproceedings{carr2000towards,
  author = {Robert D. Carr and Santosh Vempala},
  title = {{Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem}},
  booktitle = {SODA},
  year = {2000},
}

Loading related content...

Figure