3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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 rjlipton.wordpress.com/2009/03/04/ron-graham-gives-a-talk $\endgroup$ – Sasho Nikolov Oct 29 '13 at 16:37
  • 4
    $\begingroup$ For reference for the sum of square roots problem cs.smith.edu/~orourke/TOPP/P33.html, with partial results known $\endgroup$ – Sasho Nikolov Oct 29 '13 at 17:18
  • 3
    $\begingroup$ I'm upvoting because this is very much still an unsolved (and therefore research level) problem — see Sasho's "for reference" comment. $\endgroup$ – David Eppstein Oct 29 '13 at 21:49
  • 4
    $\begingroup$ Even a stopped clock is right twice a day. $\endgroup$ – David Eppstein Oct 30 '13 at 17:54
  • 3
    $\begingroup$ 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. $\endgroup$ – Kaveh Oct 31 '13 at 1:38
8
$\begingroup$

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.

$\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.