A simple LP relaxation for the asymmetric traveling salesman problem
成果类型：
Article
署名作者：
Thanh Nguyen
署名单位：
Northwestern University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-012-0544-9
发表日期：
2013
页码：
549-559
关键词：
摘要：
It is a long-standing open question in combinatorial optimization whether the integrality gap of the subtour linear program relaxation (subtour LP) for the asymmetric traveling salesman problem (ATSP) is a constant. The study on the structure of this linear program is important and extensive. In this paper, we give a new and simpler LP relaxation for the ATSP. Our linear program consists of a single type of constraints that combine both the subtour elimination and the degree constraints in the traditional subtour LP. As a result, we obtain a much simpler relaxation. In particular, it is shown that the extreme solutions of our program have at most 2n - 2 non-zero variables, improving the bound 3n - 2, proved by Vempala and Yannakakis, for the ones obtained by the subtour LP. Nevertheless, the integrality gap of the new linear program is larger than that of the traditional subtour LP by at most a constant factor.
来源URL：