7
$\begingroup$

Given a metric TSP with integer edge cost upper-bounded by a constant $C_{\max}$, can we find an poly-time algorithm solving this TSP instance?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

No polynomial-time algorithm exists, unless P=NP.

Indeed, even for TSP instances where all distances are $1$ or $2$ (note that these automatically satisfy the triangle inequality), Engebretsen and Karpinski showed that it is NP-hard to approximate TSP within a factor of $\frac{741}{740} - \epsilon$, for any $\epsilon > 0$.

Improve this answer
$\endgroup$

You must log in to answer this question.