On the Integrality Gap of the Subtour LP for the 1,2-TSP

Details On the Integrality Gap of the Subtour LP for the 1,2-TSP On the Integrality Gap of the Subtour LP for the 1,2-TSP

2011-07-08

arxiv.org/abs/1107.1630v2

Computer Science

Data Structures and Algorithms

Scientific paper

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. For the case when all edge costs $c(i,j)\in\{1,2\}$, we can show that the integrality gap is at most $106/81 \approx 1.31 < 4/3$; 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. In the case the solution to the subtour LP is a fractional 2-matching, we can show that the gap is at most 7/6; if the solution to the subtour LP is a unique fractional 2-matching, we can show that the gap is at most 10/9, and this is tight. We also perform computational experiments that show that the gap is at most 10/9 for $n \leq 10$.

Affiliated with

Also associated with

No associations

Rating

On the Integrality Gap of the Subtour LP for the 1,2-TSP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Integrality Gap of the Subtour LP for the 1,2-TSP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Integrality Gap of the Subtour LP for the 1,2-TSP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-222341