<p>Are you asking about lower or upper bounds on the integrality gap? For lower bounds, we know that the gap is at least 4/3. That example that shows this is planar, graphic, and Euclidean (well each of these is a special case of the other). So the lower bound is the same for all of them. In terms of upper bounds, as @Gamwow said, there is Gutekunst and Williamson's result on circulants, and you know the 7/5-bound on graphic TSP. You mention &quot;one special case where the extreme points are all half integral&quot; which I think is referring to the result of Shayan Oveis Gharan, Anna Karlin, and a student of theirs, Nathan Klein. I believe those three have a paper on arxiv claiming to have extended that result to all (metric) TSP, but the improvement is very small.</p>

CC BY-SA 4.0
2022-02-14T12:54:51.557Z
The final result you mention gives a slightly improved result for metric TSP, but does not improve the known integrality gap of the standard LP relaxation. As far as I'm aware it's still plausible that the LP has a 3/2 integrality gap for metric instances even though alternate algorithms may achieve substantially better constant factor approximations.
Yonatan N
CC BY-SA 4.0
2022-02-15T14:42:03.827Z
I think you were looking at an earlier paper by those authors. I'm referring to this one https://arxiv.org/abs/2105.10043
NaturalLogZ
CC BY-SA 4.0
2022-01-11T02:21:29.280Z
2022-01-11T02:21:29.280Z
NaturalLogZ
<p>What is known about the LP gap of (the natural Held-Karp relaxation of) the    (symmetric) Travelling salesman in special instances?</p>
<p>I'm only aware of one special case where the extreme points are all half integral and a 7/5 in the graphic case.
Is anything better than 3/2 known for say planar, euclidean, bounded treewidth/branchwidth or other easy instances?</p>
<p>What are the simplest instances for which the LP gap is not yet known?
References/surveys appreciated.</p>

CC BY-SA 4.0
2021-12-19T19:16:09.740Z
Samuel Gutekunst and David Williamson have analyzed the integrality gap of the subtour  LP on circulants: https://arxiv.org/abs/1902.06808
Gamow
<reference-request><linear-programming><tsp><integrality-gap>
What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?
Hao S
# What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

(Asked by: username_0 on 2021-12-19)

What is known about the LP gap of (the natural Held-Karp relaxation of) the (symmetric) Travelling salesman in special instances?

I'm only aware of one special case where the extreme points are all half integral and a 7/5 in the graphic case.
Is anything better than 3/2 known for say planar, euclidean, bounded treewidth/branchwidth or other easy instances?

What are the simplest instances for which the LP gap is not yet known?
References/surveys appreciated.

**Tags:** reference-request, linear-programming, tsp, integrality-gap

> **Comments:**
> **username_1**: Samuel Gutekunst and David Williamson have analyzed the integrality gap of the subtour  LP on circulants: https://arxiv.org/abs/1902.06808  

---

## 1 answers

### Answer by username_2 on 2022-01-11. Score: 1

Are you asking about lower or upper bounds on the integrality gap? For lower bounds, we know that the gap is at least 4/3. That example that shows this is planar, graphic, and Euclidean (well each of these is a special case of the other). So the lower bound is the same for all of them. In terms of upper bounds, as @Gamwow said, there is Gutekunst and Williamson's result on circulants, and you know the 7/5-bound on graphic TSP. You mention "one special case where the extreme points are all half integral" which I think is referring to the result of Shayan Oveis Gharan, Anna Karlin, and a student of theirs, Nathan Klein. I believe those three have a paper on arxiv claiming to have extended that result to all (metric) TSP, but the improvement is very small.

> **Comments:**
> **username_3**: The final result you mention gives a slightly improved result for metric TSP, but does not improve the known integrality gap of the standard LP relaxation. As far as I'm aware it's still plausible that the LP has a 3/2 integrality gap for metric instances even though alternate algorithms may achieve substantially better constant factor approximations.  
> **username_2**: I think you were looking at an earlier paper by those authors. I'm referring to this one https://arxiv.org/abs/2105.10043  

---

