1
$\begingroup$

Consider a set of $n$ real-valued number pairs: $(x_1,y_1), (x_2,y_2), \dots, (x_n,y_n)$. I want to find a permutation $p$ of the indices which minimizes the sum of consecutive absolute differences:

$$\sum_{j=1}^{n-1} |x_{p(j+1)} - x_{p(j)}| + \sum_{j=1}^{n-1} |y_{p(j+1)} - y_{p(j)}|.$$

I suspect this is reducible to a well known problem, so I'm looking for pointers to literature mainly, but would be happy to see a clever algorithm for doing this from scratch.

Intuitively, I want to shuffle the observations so that the graph of $x$ elements against the index is smooth looking and the same graph of the $y$ elements is also smooth looking. If I cared only about one or the other, I could simply sort with respect to those elements. I want to shuffle in such a way that I compromise between the two coordinates.

My motivation is a statistical problem of estimating a smooth curve in the plane by assuming that the coordinate dimensions are each smooth functions of an unrecorded "time index". The above problem is maximizing the smoothness of the observed data under the assumption of evenly spaced observations in time.

$\endgroup$
2
  • 1
    $\begingroup$ This sounds like you want a Hamiltonian path in the $L^1$ metric on $\R^2$ of shortest length. $\endgroup$ Jan 23, 2013 at 18:19
  • $\begingroup$ Yeah, I just remembered that the last time I thought about this I realized it could be formulated as a traveling salesman type problem. I need to go look at algorithms tailored to the version in the plane. $\endgroup$
    – R Hahn
    Jan 23, 2013 at 18:21

2 Answers 2

6
$\begingroup$

This is known in complexity circles as rectilinear TSP. Technically this is a path version TSP rather than the more common tour. In any of these specific settings, this is known to be NP-complete since the 70s (see Papadimitriou's paper).

However, unlike some NP-hard problems, Euclidean and rectilinear TSP admit a polynomial-time approximation scheme: one can obtain a tour of cost at most $(1+\epsilon)$ times optimal in time $O(n (\log n)^{O(1/\epsilon)})$. See Arora's web page for some of the key papers on this subject. You'll also find there a nice survey on approximation results (postscript link), outlining the key ideas.

The survey mentions a subexponential $2^{O(\sqrt{n})}$ exact algorithm for the Euclidean case by Smith (1988). While I would not be surprised if it adapts readily to $L^1$, I don't know enough about it to say for certain.

$\endgroup$
1
$\begingroup$

Here is something to try. Even if it fails, knowing why it fails might be useful.

Consider the Steiner tree joining your set of points. It should have minimal length and can give you a goal. If the Steiner tree has branches at points that are not on your vertex set, consider a tour that does one subtree followed by the other subtree followed by the last subtree in decreasing order of branch length.

Now that I think on it, there is potential for enough triple branch points that you might be able to reduce something like exact three cover to this problem. Locally, though, you might consider Steiner tree suggestions as to order. If not Steiner tree, then whatever tree is suggested by the Manhattan metric.

EDIT: indeed, months in the laboratory can save hours spent in the library. As Gerry Myerson suggests in his comment, there are computationally infeasible problems related to Steiner trees, and I have likely suggested one above. Moreover, the problem of rectilinear Steiner trees has been studied, thus giving more search terms for the original poster to use. Even so, there are good approximations to some Steiner tree problems, and I suspect this problem will be similar. END EDIT.

Gerhard "As Lovely As A Tree" Paseman, 2013.01.23

$\endgroup$
3
  • 1
    $\begingroup$ As a wicked test case, take the vertices of some not too small iterate of Sierpinski's triangle, rotated to produce distinct x and y coordinates, and see what you get. Gerhard "Maybe You Get A Paper" Paseman, 2013.01.23 $\endgroup$ Jan 23, 2013 at 20:53
  • $\begingroup$ How do you propose to find the Steiner tree? That's already computationally infeasible, no? $\endgroup$ Jan 23, 2013 at 23:04
  • $\begingroup$ I don't know. I believe a greedy algorithm can find a Steiner tree, at least a local minimum, by adding one vertex at a time. At the time of posting the answer, I thought a global minimum could be found in polytime, and was feasible. Gerhard "Others Can Make Trees Too" Paseman, 2013.01.23 $\endgroup$ Jan 23, 2013 at 23:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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