# Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3?

Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.

• 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. – Suresh Venkat Apr 18 '11 at 3:42
• Yes, sorry about that, I was referring to Metric TSP (for the general case). I just corrected that. – N27 Apr 18 '11 at 3:53

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)

• "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? – Kaveh Apr 19 '11 at 4:57
• Your are right, it would also fine to come up with a better LP (which would also be a major breakthrough). – 5501 Apr 19 '11 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

• thanks, nice paper. I will take a look at it, though my initial question was referring to general graphs. Regards – N27 Apr 18 '11 at 6:01