<p>It is an open problem to lower bound the difference between two distinct Euclidean TSP tours by an inverse polynomial in the input size. Such a lower bound would show that Euclidean TSP is an NP optimizaition problem, which is not known. </p>

<p>Let us assume that a Euclidean TSP instance is given by a collection of points in $(\mathbb{Z} \cap [-N, N])^2$ (i.e. points with integer coordinates bounded in absolute value by $N$). It is not known how to decide the following problem in polynomial time: given two tours $T_1$, $T_2$ over the same set of points, is the cost $c(T_1)$ of $T_1$ less than the cost $c(T_2)$ of $T_2$. To solve this problem it is sufficient to upper bound $-\log |c(T_1) - c(T_2)|$ by a polynomial in n and $\log N$, which is equivalent to your question. </p>

<p>The even more basic problem of deciding if $\sum_{i = 1}^n{\sqrt{a_i}} &lt; \sum_{i = 1}^n{\sqrt{b_i}}$, for $a_i, b_i \in \mathbb{Z} \cap [1, N]$ (i.e. positive integers bounded by $N$) in time polynomial in $n$ and $\log N$ is also open, see <a href="http://cs.smith.edu/~orourke/TOPP/P33.html">http://cs.smith.edu/~orourke/TOPP/P33.html</a>. </p>

<p>If all distances between points are rational, i.e. $\|v_i - v_j\| = a_{i,j}/b_{i,j}$ for integers $a_{ij}$, $b_{i,j}$, then 
$$
|c(T_1) - c(T_2)| &gt;= \frac{1}{\text{LCM}(\{b_{i,j}\}_{i, j \in [n]})},
$$ 
where LCM is the least common multiple function.</p>

CC BY-SA 3.0
2013-10-29T22:31:52.970Z
2013-10-29T22:31:52.970Z
Sasho Nikolov
<p>I have Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.</p>

<p>I am trying to solve TSP with brute algorithm, and I want to know how to calculate the smallest possible difference between the paths that I find during the run.</p>

<p><strong>Edit:</strong>
I want to know this, to proper round my distances. May be I can use integers, may be I need floats, or maybe I need 1,000,000 floating point number. When I am comparing two distances and I coming to the conclusion that they are equal I want to be <strong>100%</strong> sure they are.</p>

<p><strong>Edit 2</strong> Another interesting example for the possibilities is: If you are taking a graph that all the weights are 1 or 2. The minimum offset will be exactly 1.</p>

CC BY-SA 3.0
2013-10-29T16:37:56.900Z
Ok let me delete my comments, I was wrong. In fact, if there was a polynomial (in input size) lower bound, this would imply that exact euclidean TSP is an NP optimization problem, which is not known. this is related to the sum of squares problem, see e.g. the blog post http://rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk/
Sasho Nikolov
CC BY-SA 3.0
2013-10-29T16:48:49.737Z
@SashoNikolov read my comment number 2, some times it is very easy to tell.
Ilya Gazman
CC BY-SA 3.0
2013-10-29T16:51:12.917Z
How are the points specified in the input? It seems that this question is more about exact computation than TSP.
Huck Bennett
CC BY-SA 3.0
2013-10-29T17:04:51.010Z
if all distances are rational numbers, then the inverse of the LCM of the denominators is a lower bound. the problem is, even for integer coordinate points, the distances can be irrational.
Sasho Nikolov
CC BY-SA 3.0
2013-10-29T17:18:00.310Z
For reference for the sum of square roots problem http://cs.smith.edu/~orourke/TOPP/P33.html, with partial results known
Sasho Nikolov
CC BY-SA 3.0
2013-10-29T21:49:21.193Z
I'm upvoting because this is very much still an unsolved (and therefore research level) problem — see Sasho's "for reference" comment.
David Eppstein
CC BY-SA 3.0
2013-10-30T17:16:09.200Z
@David, I don't think being open is a suitable criteria by itself. The user has been claiming to have a polynomial time algorithm for TSP while the evidence shows that he is not even familiar with basics. See [1](http://cs.stackexchange.com/questions/14902/traveling-salesman-problem-solution-with-polynomial-algorithm) and [2](http://cstheory.stackexchange.com/q/19342/).
Kaveh
CC BY-SA 3.0
2013-10-30T17:54:44.220Z
Even a stopped clock is right twice a day.
David Eppstein
CC BY-SA 3.0
2013-10-30T19:11:44.213Z
@Kaveh You do not follow all my post. I been claiming this before and I know that was a mistake. How ever I did not stop trying, the only difference is that now I know that I did not succeeded yet, and may never will. But I am investing in to this all my time, and I came to some very interesting things.
Ilya Gazman
CC BY-SA 3.0
2013-10-31T01:30:29.453Z
@Babibu, It is clear from this post that you don't know even the basics. I am not talking about the question answered by Sasho, no one who knows basic complexity theory would state things like "maybe I need 1,000,000 floating point number". You haven't even stated this question in a reasonably precise way and it is clear you lack elementary mathematical training and algorithms/complexity theory knowledge.
Kaveh
CC BY-SA 3.0
2013-10-31T01:38:44.850Z
cstheory is a Q&A site for professional researchers in TCS and related fields (which typically means people who have or peruse a PhD). It is not for cranks or hobbyist who don't know the basics but seek help in their attempts to solve famous open problems.
Kaveh
<graph-theory><graph-algorithms><shortest-path><hamiltonian-paths>
Minimum offset while measuring TSP paths
Ilya Gazman
# Minimum offset while measuring TSP paths

(Asked by: username_0 on 2013-10-29)

I have Euclidean graph: each vertex is a point on the 2D plane, so the weight of each edge is the Euclidean distance between the vertices.

I am trying to solve TSP with brute algorithm, and I want to know how to calculate the smallest possible difference between the paths that I find during the run.

**Edit:**
I want to know this, to proper round my distances. May be I can use integers, may be I need floats, or maybe I need 1,000,000 floating point number. When I am comparing two distances and I coming to the conclusion that they are equal I want to be **100%** sure they are.

**Edit 2** Another interesting example for the possibilities is: If you are taking a graph that all the weights are 1 or 2. The minimum offset will be exactly 1.

**Tags:** graph-theory, graph-algorithms, shortest-path, hamiltonian-paths
> **Comments:**
> **username_1**: Ok let me delete my comments, I was wrong. In fact, if there was a polynomial (in input size) lower bound, this would imply that exact euclidean TSP is an NP optimization problem, which is not known. this is related to the sum of squares problem, see e.g. the blog post http://rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk/  
> **username_0**: @SashoNikolov read my comment number 2, some times it is very easy to tell.  
> **username_2**: How are the points specified in the input? It seems that this question is more about exact computation than TSP.  
> **username_1**: if all distances are rational numbers, then the inverse of the LCM of the denominators is a lower bound. the problem is, even for integer coordinate points, the distances can be irrational.  
> **username_1**: For reference for the sum of square roots problem http://cs.smith.edu/~orourke/TOPP/P33.html, with partial results known  
> **username_3**: I'm upvoting because this is very much still an unsolved (and therefore research level) problem — see Sasho's "for reference" comment.  
> **username_4**: @David, I don't think being open is a suitable criteria by itself. The user has been claiming to have a polynomial time algorithm for TSP while the evidence shows that he is not even familiar with basics. See [1](http://cs.stackexchange.com/questions/14902/traveling-salesman-problem-solution-with-polynomial-algorithm) and [2](http://cstheory.stackexchange.com/q/19342/).  
> **username_3**: Even a stopped clock is right twice a day.  
> **username_0**: @Kaveh You do not follow all my post. I been claiming this before and I know that was a mistake. How ever I did not stop trying, the only difference is that now I know that I did not succeeded yet, and may never will. But I am investing in to this all my time, and I came to some very interesting things.  
> **username_4**: @Babibu, It is clear from this post that you don't know even the basics. I am not talking about the question answered by Sasho, no one who knows basic complexity theory would state things like "maybe I need 1,000,000 floating point number". You haven't even stated this question in a reasonably precise way and it is clear you lack elementary mathematical training and algorithms/complexity theory knowledge.  
> **username_4**: cstheory is a Q&A site for professional researchers in TCS and related fields (which typically means people who have or peruse a PhD). It is not for cranks or hobbyist who don't know the basics but seek help in their attempts to solve famous open problems.  

---

## 1 answers

### Answer by username_1 on 2013-10-29. Score: 8 | Accepted answer

It is an open problem to lower bound the difference between two distinct Euclidean TSP tours by an inverse polynomial in the input size. Such a lower bound would show that Euclidean TSP is an NP optimizaition problem, which is not known.

Let us assume that a Euclidean TSP instance is given by a collection of points in $(\mathbb{Z} \cap [-N, N])^2$ (i.e. points with integer coordinates bounded in absolute value by $N$). It is not known how to decide the following problem in polynomial time: given two tours $T\_1$, $T\_2$ over the same set of points, is the cost $c(T\_1)$ of $T\_1$ less than the cost $c(T\_2)$ of $T\_2$. To solve this problem it is sufficient to upper bound $-\log |c(T\_1) - c(T\_2)|$ by a polynomial in n and $\log N$, which is equivalent to your question.

The even more basic problem of deciding if $\sum\_{i = 1}^n{\sqrt{a\_i}} < \sum\_{i = 1}^n{\sqrt{b\_i}}$, for $a\_i, b\_i \in \mathbb{Z} \cap [1, N]$ (i.e. positive integers bounded by $N$) in time polynomial in $n$ and $\log N$ is also open, see <http://cs.smith.edu/~orourke/TOPP/P33.html>.

If all distances between points are rational, i.e. $\|v\_i - v\_j\| = a\_{i,j}/b\_{i,j}$ for integers $a\_{ij}$, $b\_{i,j}$, then
$$
|c(T\_1) - c(T\_2)| >= \frac{1}{\text{LCM}(\{b\_{i,j}\}\_{i, j \in [n]})},
$$
where LCM is the least common multiple function.


---

