-1
$\begingroup$

Is it possible to calculate, efficiently, the minimum tour distance for TSP? That is, the distance without having to provide the actual tour.

If this is not possible (I assume it is not), how tight a lower bound can we efficiently calculate?

$\endgroup$
4
$\begingroup$

When we say that TSP is hard to approximate up to a factor $\alpha$, this means that if there was an algorithm for TSP which always outputs a number in $[OPT,\alpha OPT]$ then P=NP (here OPT is the length of the minimal tour). The algorithm doesn't have to find a tour of this length.

Even more formally, what these results (probably) show is that there is a many-one reduction $f$ from 3SAT to TSP such that for a 3CNF $\varphi$, if $\varphi$ is satisfiable then the optimal tour of $f(\varphi)$ has length at most $1$, while if $\varphi$ is unsatisfiable then the optimal tour of $f(\varphi)$ has length at least $\alpha$. So if you could tell between these two cases, then P=NP.

See this list of hardness of approximation results for various variants of TSP.

$\endgroup$
3
$\begingroup$

Computing the length of the shortest tour is NP-hard: using it, you could solve the decision version of TSP (given the distance matrix and a target $k$, is there a tour of length at most $k$?), which is one of the standard NP-complete problems.

Approximation is covered by the Wikipedia article on TSP, which you should have checked before asking here. Essentially, approximation is hard in general but, for metric TSP (the version where the distances obey the triangle inequality), you can get within a factor of 1.5 of the optimal tour.

$\endgroup$
3
$\begingroup$

The question seems only for a lower bound rather than an approximation algorithm, although they are similar. For estimating a lower bound, you can use $TSP\geq \max\{MST,2\times MM\}$, where MM is the minimum perfect matching. Indeed this lower bound is used to develop the 3/2-approximation for the metric case but the lower bound works even for non-metric cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.