4
$\begingroup$

The travelling salesman problem (TSP) is well-known, see e.g. https://en.wikipedia.org/wiki/Travelling_salesman_problem.

Let us consider the Euclidean version of the TSP within the unit square. This means the metric is Euclidean and we only allow for cities within $[0,1]^2$.

The question I am interested in is: What are the worst cases of city positions with respect to the optimal solution of the TSP? I am interested in both, asymptotic results but also an algorithms that determine such sets (or sets, which are almost as bad as possible) for finite numbers of cities.

The length of an optimal TSP tour on a worst point set in $[0,1]^d$ with n points (let us call it $l^{(n)}$) is proven to be $\theta(n^{(d-1)/d})$ where $d$ is the dimension, so here, as we look at the two-dimensional unit square we have $l=\theta(n^{1/2})$. To see that there are such point sets where the optimal tour is $\Omega(n^{1/2})$ one can consider rectangular lattices. (See the paper of Snyder and Steele and references inthere.)

However, I am interested in how the point sets look like. Asymptoticlly, it might be intuitive to assume that the cities are somehow equidistributed. Indeed in the referenced paper of Snyder and Steele, they show that this is the case in the following sense:

For any $n \in \mathbb N$ let $S^{(n)}$ be a worst-case point set with $n$ points. Let $R \subseteq [0,1]^2$ be any rectangle in the unit square with area $A(R)$. Then the following conclusion holds: $ \lim\limits_{n \rightarrow \infty} \frac{1}{n} |S^{(n)} \cap R| = A(R)$.

Note that two years later they generalized this result to higher dimensions, using a different approach.

I have four questions:

  1. "How unique" are sets (or more precisely sequences of sets of increasing size, as we want to make asymptotical statements), that fulfill the "uniformness condition" of the conclusion of the theorem?
  2. Are there any algorithms known for the finite-case (i.e. non-asymptotical) which provide point-sets which are provably close to "worst-possible"?
  3. In the asymptotical case, is the reverse direction also true in the sense, that every sequence of sets of increasing size that fulfills the "uniformness condition" of the theorem is also asymptotically worst-case? This is related with 1.
  4. More general, what are further references to this topic. What has been found since the paper from Snyder and Steele which is from 1993?

Thanks in advance!

Timothy Law Snyder and J. Michael Steele, MR 1213258 Equidistribution of point sets for the traveling salesman and related problems, Proceedings of the {F}ourth {A}nnual {ACM}-{SIAM} {S}ymposium on {D}iscrete {A}lgorithms ({A}ustin, {TX}, 1993) (1993), 462--466.

$\endgroup$
4
$\begingroup$

Here is one paper that in some sense follows upon the Snyder-Steele paper you cite:

Carlsson, John Gunnar, and Mehdi Behroozi. "Earth mover’s distance and the distributionally robust TSP." (2015). (PDF download.)

In this paper, we consider a distributionally robust version of the Euclidean travelling salesman problem (TSP): as input, we are given a compact, contiguous planar region $R$ and a realization of sampled demand points in that region, and our objective is to construct a probability distribution on $R$ whose induced TSP tour (...) is as long as possible while remaining sufficiently “close” to the empirical distribution consisting of the sampled points.


         
          (Fig.5b from Carlsson-Behroozi: "the worst-case workloads among all 4 pieces are equal")


$\endgroup$
  • $\begingroup$ Thank you, this seems interesting! I will read the paper. Unfortunately I do not have enough reputation to upvote your answer already. If I have enough, I will upvote it! $\endgroup$ – modnar Sep 5 '16 at 11:47
3
$\begingroup$

The only part I can answer definitively is #3, to which the answer is "no". If you place points in a square grid, the TSP tour is shorter than if you place points in a hexagonal lattice, but both satisfy the uniformness condition. As for #1, I think that the hexagonal lattice is conjectured to be the actual worst-case asymptotic distribution, but am unaware of any proof.

You are probably aware of the following other references, which may be helpful:

L. A. Goddyn. Quantizers and the worst-case euclidean traveling salesman problem. Journal of Combinatorial Theory, Series B, 50(1):65–81, 1990.

H. J. Karloff. How long can a euclidean traveling salesman tour be? SIAM Journal on Discrete Mathematics, 2(1):91–99, 1989.

K. J. Supowit, E. M. Reingold, and D. A. Plaisted. The travelling salesman problem and minimum matching in the unit square. SIAM Journal on Computing, 12(1):144–156, 1983.

$\endgroup$
  • $\begingroup$ that the hexagonal grid is the worst case would immediately follow from the fact, that it is the densest packing of circles in the plane. $\endgroup$ – Manfred Weis Sep 8 '16 at 7:20
  • 1
    $\begingroup$ It is not as simple as that. Although the bit about hexagons seems intuitively obvious, the references I wrote above show previous attempts to make progress towards this conjecture. $\endgroup$ – John Gunnar Carlsson Sep 8 '16 at 7:55
3
$\begingroup$

Instances with long shortest tours can be obtained from the optimal solutions to packing $n$ circles of largest equal radius into a square or, can be derived from such solutions via appropriate scaling of the square and, by increasing the radius of so called "rattlers" (i.e. circles, whose position isn't fixed).

A lower bound for the length of such tours is the sum of circle diameters; the optimal tour can however be longer, if the contact graph of the circles isn't Hamiltonian.

The heuristic reason why circle packings are good sources for long optimal tours is that they maximize the minimal distance between the cities.
When fixing the total area of a set of circles, the sum of their radii is maximal if all circles have equal size. There are very many optimal solutions of the circle packing problem depicted here

The basic idea of using solutions to circle packing problem instances directly carries over to other types of region (e.g. cities inside a circle), higher dimensions or other metrics or even to other spaces (e.g. longest shortest tours visiting $n$ cities on a sphere).

$\endgroup$
  • $\begingroup$ I am not yet convinced: 1) What justifies the "fixing the total area assumption?" 2) With "empty disk" you mean that no other city is inside? 3) Take $n=2$. Then the worst-case point set shoul be to place the cities in two corners like e.g. left upper and right lower corner. However, these corners are not centers of any disks with non-zero radius. But I also might have misunderstood something. And intuitively I agree, that looking at circles seems to be somehow related. $\endgroup$ – modnar Sep 8 '16 at 16:37
  • $\begingroup$ @modnar I see, that I have to clarify my answer in some points: first is how to transfer the solution to circles in square packing to a point in squares instance: letting $r$ be the radius of the spheres, centrally (i.e. w.r.t. the center of the unit square) scaling by $\frac{1}{1-r}$ moves the outer circle's centers onto the boundary of the unit square, making the circle centers a instance of the kind of problem that your question is aimed at. For addressing the other questions, I will edit my answer (if you think it still makes sense). $\endgroup$ – Manfred Weis Sep 9 '16 at 18:09
  • $\begingroup$ Thanks for editing your post, I think using circles that way is a good idea. However, do you think with this approach "optimality" (in the worst-case-sense) of hexagonal grids can be proven? I do not yet see how. $\endgroup$ – modnar Sep 10 '16 at 8:49
  • 1
    $\begingroup$ I think that has been already tried without success and I only see a chance in proving that denser circle packings (with circles of different sizes) yield shorter tours for the same number of circles (cf e.g. this article by Tom Kennedy). I don't know,(and wouldn't be surprised) if that has been already checked. $\endgroup$ – Manfred Weis Sep 10 '16 at 12:54

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.