A Simple LP Relaxation for the Asymmetric Travelin

Authors: Thành Nguyen

Publish Date: 2008/8/25

Volume: , Issue: , Pages: 207-218

PDF Link

Abstract

A longstanding conjecture in Combinatorial Optimization is that the integrality gap of the HeldKarp LP relaxation for the Asymmetric Traveling Salesman Problem ATSP is a constant In this paper we give a simpler LP relaxation for the ASTP The integrality gaps of this relaxation and of the HeldKarp relaxation are within a constant factor of each other Our LP is simpler in the sense that its extreme solutions have at most 2n − 2 nonzero variables improving the bound 3n − 2 proved by Vempala and Yannakakis for the extreme solutions of the HeldKarp LP relaxation Moreover more than half of these nonzero variables can be rounded to integers while the total cost only increases by a constant factor

Keywords: