5
$\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.

Improve this question
$\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
    Commented Dec 19, 2021 at 19:16

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$
2
  • 1
    $\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
    Commented Feb 14, 2022 at 12:54
  • 1
    $\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$
    – NaturalLogZ
    Commented Feb 15, 2022 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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