Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.
4
$\begingroup$
$\endgroup$
-
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 Venkat Apr 18 '11 at 3:42
-
$\begingroup$ Yes, sorry about that, I was referring to Metric TSP (for the general case). I just corrected that. $\endgroup$ – N27 Apr 18 '11 at 3:53
5
$\begingroup$
$\endgroup$
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$ – Kaveh Apr 19 '11 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$ – 5501 Apr 19 '11 at 10:02
3
$\begingroup$
$\endgroup$
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
answered Apr 18 '11 at 4:13
-
$\begingroup$ thanks, nice paper. I will take a look at it, though my initial question was referring to general graphs. Regards $\endgroup$ – N27 Apr 18 '11 at 6:01
