sorting two paired lists of real numbers to minimize consecutive absolute differences

Question

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.

Answer 1

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.

Answer 2

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