What is known about (upper bounds on) the LP gap of the (symmetric) Travelling salesman in special instances?

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.

• Samuel Gutekunst and David Williamson have analyzed the integrality gap of the subtour LP on circulants: arxiv.org/abs/1902.06808 Dec 19, 2021 at 19:16

1 Answer

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.

• 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. Feb 14, 2022 at 12:54
• I think you were looking at an earlier paper by those authors. I'm referring to this one arxiv.org/abs/2105.10043 Feb 15, 2022 at 14:42