4
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ Samuel Gutekunst and David Williamson have analyzed the integrality gap of the subtour LP on circulants: arxiv.org/abs/1902.06808 $\endgroup$
    – Gamow
    Dec 19, 2021 at 19:16

1 Answer 1

0
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.