What is known about worst-case point sets for the travelling salesman problem?

Question

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.

Answer 1

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")}

---

Answer 2

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.

Answer 3

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).