On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems (Q1885277)

The paper interrelates the approximabilities of the metric STSP (Symmetric Traveling Salesman Problem) and the metric ATSP (Asymmetric Traveling Salesman Problem) via the Held-Karp linear programming relaxation of the metric STSP, for which an integrality gap of \(4/3\) was conjectured. Using a new characterization of the integrality gap for general linear objective functions over polyhedra together with the definition of ultra-fundamental, hard-to-round STSP extreme points, it is shown that a slight strengthening of the Held-Karp conjecture would imply also a tight \(4/3\) integrality gap for the metric ATSP.