On the integrality gap of the subtour LP for the 1,2-TSP

DOI10.1007/S10107-014-0835-4MaRDI QIDQ2340281zbMATH OpenOpenAlexFDO

Authors Jiawei Qian, Frans Schalekamp, David P. Williamson, Anke van Zuylen

Publication date 16 April 2015

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1107.1630

zbMATH Keywords

integrality gaplinear programmingsubtour eliminationtraveling salesman problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Linear programming (90C05) Combinatorial optimization (90C27)

Abstract: In this paper, we study the integrality gap of the subtour LP relaxation for the traveling salesman problem in the special case when all edge costs are either 1 or 2. For the general case of symmetric costs that obey triangle inequality, a famous conjecture is that the integrality gap is 4/3. Little progress towards resolving this conjecture has been made in thirty years. We conjecture that when all edge costs $c_{ij}in1,2$, the integrality gap is $10/9$. We show that this conjecture is true when the optimal subtour LP solution has a certain structure. Under a weaker assumption, which is an analog of a recent conjecture by Schalekamp, Williamson and van Zuylen, we show that the integrality gap is at most $7/6$. When we do not make any assumptions on the structure of the optimal subtour LP solution, we can show that integrality gap is at most $5/4$; this is the first bound on the integrality gap of the subtour LP strictly less than $4/3$ known for an interesting special case of the TSP. We show computationally that the integrality gap is at most $10/9$ for all instances with at most 12 cities.

Recommendations

• On the integrality gap of the subtour LP for the 1,2-TSP
• Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
• On the integrality ratio of the subtour LP for Euclidean TSP
• Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture

Cites work

• A Randomized Rounding Approach to the Traveling Salesman Problem

Cited in

(14)

• Improved integrality gap upper bounds for traveling salesperson problems with distances one and two
• On the integrality ratio of the subtour LP for Euclidean TSP
• A note on the integrality gap of the configuration LP for restricted Santa Claus
• The salesman's improved tours for fundamental classes
• Hard to solve instances of the Euclidean traveling salesman problem
• The saleman's improved tours for fundamental classes
• On the integrality gap of the subtour LP for the 1,2-TSP
• Finding the exact integrality gap for small traveling salesman problems
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• scientific article; zbMATH DE number 2086915 (Why is no real title available?)
• 2-matchings, the traveling salesman problem, and the subtour LP: a proof of the Boyd-Carr conjecture
• Characterizing the integrality gap of the subtour LP for the circulant traveling salesman problem
• TSP tours in cubic graphs: beyond 4/3
• A proof of the Boyd-Carr conjecture

Describes a project that uses

Uses Software

• CPLEX

This page was built for publication: On the integrality gap of the subtour LP for the 1,2-TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2340281)