<p>I've began studying some CS recently, and I've faced the TSP.
The decision problem version of the TSP is NP-complete, right?
I've noticed (and elaborated myself) that there exists several polynomial time
approximations for the TSP. Combined with the decision problem, this "lowers"
the complexity of the algorithm for some values given for the decision, because
those values may lie outside of the estimation: say the decision asks for a path no longer
than 50 and we find a path of 150 which is at most 2x the minimum path, then we would 
only need polynomial time for evaluating it. </p>

<p>So my question is as follows: is it
possible to assemble algorithms with polynomial time (with any polynomial order) that
 approximate the TSP to a given ratio? Because then, I could be able to add a series
of algorithms before the actual non-polynomial time algorithm to progressively lower it's
complexity. Assembling this series of algorithms to find the exact solution would probably require an infinite series of polynomial time, which cannot have polynomial time as a whole. But I think it is possible to use tricks to limit this to a finite number, which would result in a total polynomial time for any given decision value. Think about it: the
worst case of this problem is when the decision parameter is exactly the TSP solution - 
we thus have some information about it. Since P probably differs from NP, I guess there are no such algorithms?</p>

<p>Sorry If I sound a bit confusing, I don't know If my thoughts make much sense
mathematically.</p>

CC BY-SA 3.0
2011-05-06T15:40:23.460Z
As you indicate in the question itself, the problem of determining a polynomially long series of approximations that eventually lead to an optimal solution for the TSP is as hard as the TSP itself, since a solution to the former will solve the latter.
Suresh Venkat
CC BY-SA 3.0
2011-05-07T04:23:44.870Z
The main point is the dependency of the running time on the approximation parameter $\epsilon$. If $NP \neq P$ then the dependency of the running time on the $\epsilon$ will be bad (e.g. $n^{2^{-\epsilon}}$ is bad), it will be polynomial for each fixed $\epsilon$ but the exponent will grow too quickly w.r.t. $\epsilon$. For any input $x$ one can find an $\epsilon (x)>0$ which will grantee that any $\epsilon$-approximation will be a perfect answer, so one does not need to go to limit. But when this good enough value $\epsilon(x)$ is combined with the algorithm, the result should not be in $P$.
Kaveh
<cc.complexity-theory><tsp>
Is there a series of algorithms for approximating TSP polynomially?
Real
# Is there a series of algorithms for approximating TSP polynomially?

(Asked by: username_0 on 2011-05-06)

I've began studying some CS recently, and I've faced the TSP.
The decision problem version of the TSP is NP-complete, right?
I've noticed (and elaborated myself) that there exists several polynomial time
approximations for the TSP. Combined with the decision problem, this "lowers"
the complexity of the algorithm for some values given for the decision, because
those values may lie outside of the estimation: say the decision asks for a path no longer
than 50 and we find a path of 150 which is at most 2x the minimum path, then we would
only need polynomial time for evaluating it.

So my question is as follows: is it
possible to assemble algorithms with polynomial time (with any polynomial order) that
approximate the TSP to a given ratio? Because then, I could be able to add a series
of algorithms before the actual non-polynomial time algorithm to progressively lower it's
complexity. Assembling this series of algorithms to find the exact solution would probably require an infinite series of polynomial time, which cannot have polynomial time as a whole. But I think it is possible to use tricks to limit this to a finite number, which would result in a total polynomial time for any given decision value. Think about it: the
worst case of this problem is when the decision parameter is exactly the TSP solution -
we thus have some information about it. Since P probably differs from NP, I guess there are no such algorithms?

Sorry If I sound a bit confusing, I don't know If my thoughts make much sense
mathematically.

**Tags:** cc.complexity-theory, tsp

> **Comments:**
> **username_1**: As you indicate in the question itself, the problem of determining a polynomially long series of approximations that eventually lead to an optimal solution for the TSP is as hard as the TSP itself, since a solution to the former will solve the latter.  
> **username_2**: The main point is the dependency of the running time on the approximation parameter $\epsilon$. If $NP \neq P$ then the dependency of the running time on the $\epsilon$ will be bad (e.g. $n^{2^{-\epsilon}}$ is bad), it will be polynomial for each fixed $\epsilon$ but the exponent will grow too quickly w.r.t. $\epsilon$. For any input $x$ one can find an $\epsilon (x)>0$ which will grantee that any $\epsilon$-approximation will be a perfect answer, so one does not need to go to limit. But when this good enough value $\epsilon(x)$ is combined with the algorithm, the result should not be in $P$.  

---

## 0 answers

