Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.
-
2$\begingroup$ I suspect you don't mean Euclidean TSP, since for that case there's a celebrated PTAS. If you're talking about metric TSP, you have to be careful even there, since there's at least one result that improves the Christofides heuristic to 4/3 for cubic-3-edge connected graphs. A good reference is personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf, which also shows a 7/5 approximation (and lower bound) for subcubic graphs, and personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf, that improves Christofides for metrics induced by unweighted graphs. $\endgroup$– Suresh VenkatApr 18, 2011 at 3:42
-
$\begingroup$ Yes, sorry about that, I was referring to Metric TSP (for the general case). I just corrected that. $\endgroup$– N27Apr 18, 2011 at 3:53
2 Answers
To my knowledge this is the only reason and I am not sure whether everybody in the fields agrees with this.
The optimistic reasoning is: Since there has not been any progress in getting a larger lower bound, $4/3$ is the right bound. And once we know this for sure, we "only" need a polynomial time rounding algorithm.
More pessimistic people will view the $4/3$ only as a lower bound. To beat this, you need an algorithm that does not "use" the Held-Karp relaxation, even not in a hidden way.
Even more pessimistic people would say that $3/2$ is the right bound, because nobody could improve Christofides algorithm (ignoring some of the recent progresses.)
Note that for metric ATSP, the integrality gap is at least $2 - \epsilon$ (Charikar, Goemans, Karloff, FOCS 2004)
-
$\begingroup$ "To beat this, you need an algorithm that does not "use" linear programming, even not in a hidden way." Could you elaborate on this and what you mean by "use .. in a hidden way"? AFAIU, an IG is for a relaxation of a problem, not the problem. A different relaxation might have a better IG, or am I missing something? $\endgroup$– KavehApr 19, 2011 at 4:57
-
1$\begingroup$ Your are right, it would also fine to come up with a better LP (which would also be a major breakthrough). $\endgroup$– 5501Apr 19, 2011 at 10:02
Yyou have to be careful, since there's at least one result that improves the Christofides heuristic to 4/3 for cubic-3-edge connected graphs. A good further reference is http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf, which just showed a 7/5 approximation (and lower bound) for subcubic graphs, and this result that improves Christofides for metrics induced by unweighted graphs.
The Boyd et al paper discusses this matter in its introduction
-
$\begingroup$ thanks, nice paper. I will take a look at it, though my initial question was referring to general graphs. Regards $\endgroup$– N27Apr 18, 2011 at 6:01