<p>To my knowledge this is the only reason and I am not sure whether everybody in the fields agrees with this. </p>

<p>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.</p>

<p>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. </p>

<p>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.)</p>

<p>Note that for metric ATSP, the integrality gap is at least $2 - \epsilon$
(Charikar, Goemans, Karloff, FOCS 2004)</p>

CC BY-SA 3.0
2011-04-19T04:57:47.143Z
"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
CC BY-SA 3.0
2011-04-19T10:02:48.353Z
Your are right, it would also fine to come up with a better LP (which would also be a major breakthrough).
5501
CC BY-SA 3.0
2011-04-18T10:29:03.413Z
2011-04-19T10:01:52.583Z
2011-04-19T10:01:52.583Z
5501
<p>Yyou have to be careful, since there's <a href="http://arxiv.org/abs/1101.5586" rel="nofollow">at least one result</a> that improves the Christofides heuristic to 4/3 for cubic-3-edge connected graphs. A good further reference is <a href="http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf" rel="nofollow">http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf</a>, which just showed a 7/5 approximation (and lower bound) for subcubic graphs, and <a href="http://www.stanford.edu/~shayan/Publications_files/tsp.pdf" rel="nofollow">this result</a> that improves Christofides for metrics induced by unweighted graphs.</p>

<p>The <a href="http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf" rel="nofollow">Boyd et al paper</a> discusses this matter in its introduction</p>

CC BY-SA 3.0
2011-04-18T06:01:02.553Z
thanks, nice paper. I will take a look at it, though my initial question was referring to general graphs. Regards
N27
CC BY-SA 3.0
2011-04-18T04:13:59.743Z
2011-04-18T04:13:59.743Z
Suresh Venkat
<p>Is it just that integrality gaps (LP/IP) for specific instances do not give more than 4/3? Thanks in priori.</p>

CC BY-SA 3.0
2011-04-18T03:42:19.490Z
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 http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf, which also shows a 7/5 approximation (and lower bound) for subcubic graphs, and http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf, that improves Christofides for metrics induced by unweighted graphs.
Suresh Venkat
CC BY-SA 3.0
2011-04-18T03:53:16.313Z
Yes, sorry about that, I was referring to Metric TSP (for the general case). I just corrected that.
N27
<ds.algorithms><approximation-algorithms><tsp><integrality-gap>
Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3?
N27
# Why is Metric TSP's best possible achieved approximation ratio believed to be 4/3?

(Asked by: username_0 on 2011-04-17)

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

**Tags:** ds.algorithms, approximation-algorithms, tsp, integrality-gap
> **Comments:**
> **username_1**: 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 http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf, which also shows a 7/5 approximation (and lower bound) for subcubic graphs, and http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf, that improves Christofides for metrics induced by unweighted graphs.  
> **username_0**: Yes, sorry about that, I was referring to Metric TSP (for the general case). I just corrected that.  

---

## 2 answers

### Answer by username_2 on 2011-04-18. Score: 5 | Accepted answer

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)

> **Comments:**
> **username_3**: "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?  
> **username_2**: Your are right, it would also fine to come up with a better LP (which would also be a major breakthrough).  

---

### Answer by username_1 on 2011-04-18. Score: 3

Yyou have to be careful, since there's [at least one result](http://arxiv.org/abs/1101.5586) 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](http://www.stanford.edu/~shayan/Publications_files/tsp.pdf) that improves Christofides for metrics induced by unweighted graphs.

The [Boyd et al paper](http://personal.vu.nl/r.a.sitters/papers/GraphTsp.pdf) discusses this matter in its introduction

> **Comments:**
> **username_0**: thanks, nice paper. I will take a look at it, though my initial question was referring to general graphs. Regards  

---

