Towards a 4/3 Approximation for the Asymmetric Traveling Salesman Problem
Lists
Only you see this
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...