Please see PDF version
q
I
1
i
Equidistribution in All Dimensions of
Worst-Case Point Sets for the TSP
Timothy Law Snyder'
Department of Computer Science
Georgetown University
Washington, DC 20057
J. Michael Steele 2
Department of Statistics
The Wharton School
University of Pennsylvania
Philadelphia, PA 19104
ABSTRACT
Given a set S of n points in the unit square [0, 1] d , an optimal traveling salesman tour of S is a tour of S that is of minimum length. A worst-case point set for the Traveling Salesman Problem in the unit square is a point set S(') whose optimal traveling salesman tour achieves the maximum possible length among all point sets S C [0, 1]d, where ISI = n. An open problem is to determine the structure of S(n). We show that for any rectangular parallelepiped R contained in [0, 1]d, the number of points in s(,) nR is asymptotic to n times the volume of R. Analogous results are proved for the minimum spanning tree, minimum-weight matching, and rectilinear Steiner minimum tree. These equidistribution theorems are the first results concerning the structure of worst-case point sets like S(n).
Keywords: Equidistribution, worst-case, non-linear growth, traveling salesman, rec-
tilinear Steiner tree, minimum spanning tree, minimum-weight matching.
Research supported in part by Georgetown University 1991 Summer Research Award; Georgetown University 1992 Junior Faculty Research Fellowship-, and Georgetown College John R. Kennedy, Jr. Faculty Research Fund.
2 Research supported in part by the following grants: NSF DMS92-11634 and ARO DAAL0391-G-0110.
I
i
I
AMS Subject Classifications: 68R10, 05C45, 9OC35, 68UO5
1. Introduction
In this note we show that for many problems of Euclidean combinatorial optimization, the maximal value of the objective function is attained by point sets that are asymptotically equidistributed. To facilitate exposition, we focus at first on the traveling salesman problem (TSP) for a finite set S of points in the d-dimensional unit cube [0, 1] d . Let 7-(S) denote the set of tours that span S. The optimal TSPcost of S is the value given by
TSP(S) = min E Jel, (1.1)
TEr(S) eET
where Jel denotes the Euclidean length of the edge e.
For each dimension d > 2, there axe constants Cd such that
1S1(d-1)1d'
TSP(S) < Cd (1.2)
where ISI denotes the cardinality of S. Considerable effort has been devoted to determining good bounds on Cd; the earliest bounds are due to Few (1955), and the current records are held by Karloff (1989) and Goddyn (1990). Simply by considering the rectangular lattice one can see there are also constants c' > 0 such d
that for all n > 2,
(d-l)ld
max TSP(S) > c'n (1.3)
SC[O'1]1 d
ISI=n
If we lot p,,,(n) = maxf TSP(S) : S C [0, 11d, ISI n then the usual considerations of continuity and compactness show that there are n-sets S for which TSP(S) = p,,,(n) (cf. Moran (1984), P. 115); these are the worst-case point sets referred to in our title. We suppress p,,,,'s dependence on d to keep notation simple.
The main result obtained here is that worst-case point sets are asymptotically equidistributed in the sense made explicit in the following theorem.
Theorem 1. If IS(') : 2 < n < ool is a sequence of worst-ca-se TSP p oint sets with S(n) C [0, 1]d
, d > 2, arid IS(') I - n, then for any rectangular parallelepiped
R c [0, 1]d, we have
lim _IS n n RI = VOld(R). (1.4)
n-oo n
While Theorem I is certainly intuitive, the proof we provide requires more than first principles; it relies essentially on the result of Steele and Snyder (1989) that there exist constants fld > 0 such that
lim PTSP(n) fid. (1.5)
n(d-l)/d
The exact asymptotic result (1.5) was motivated by the classical result of Beardwood, Halton, and Hammersley (1959) for the case of random point sets, and it seems to provide just the refinement of bounds like (1.2) and (1.3) that is needed to obtain equidistribution limit theorems.
We note that a proof of Theorem 1 in dimension two using techniques different from the ones we use here is given in Snyder and Steele (1993). We also note that Theorem I has a close connection to some results and a conjecture of Supowit, Reingold, and Plaisted (1983). This connection will be explained more fully in Section 4, after we have developed some notation.
In the next section we prove Theorem 1; Section 3 deals with problems other than the TSP.
2. Proof of Theorem 1
For any fixed integer m > 2, we partition [0, Ild into Md subcubes Qi, where 1 0, there is an m and sets A and B such that UAQi C R C UBQi and VOld(UiEB-AQi) :!~ IE VOld(R); hence to prove Theorem I it suffices to consider equidistribution with respect to the Qi. Specifically, it suffices to show that for each m > 2 and 1 < i :5 Md , we have
IQi n SWI I
(2.1)
n"M ;;;-d
co n
3
Our proof of (2.1) depends on the equality case of 1161der's inequality,
which tells us that for 1 < p < oo and ui, vi > 0, we have Ek I Uivi <
(Ek 1 Up) 11P (Ek I Vpl(p-1)
i= i i= i )(p_')/p. Setting vi = 1 for 1 < i :5 k, we have
Ek Ui = k Ui-1 < (E k U pylp (Ek JP/(P-'))(P-')/P = (Ek Up)11P k(P-01P.
i=1 Ei=l - i=1 i i=1 . i=1 i
The fact that is important for us is that one can have equality in this bound if and
only if ul = U2 ... = Uk (Hardy, Littlewood, and Polya (1964), pp. 21-26).
Let s(n,i) lQi n S(n) 1; i.e., s(n, i) is the number of points of a worst-case point set S(n) that appear in the the ith subcube. We first establish a limit result concerning the s(n, i) that measures their aggregate size in a way that works usefully with 1161der's inequality.
Leimma 1. For all m > 2, we have
d
E_ i)(d-l)ld
lim i=ls(n, =M. (2.2)
n~co n(d-l)/d
Proof
First write (1.5) as
PTSP(n) = Odn (d-l)ld + r(n), where r(n) = o(n (d-i)ld). (2.3)
Let W denote a closed walk on S(n) = f X 1, X 2, - - -, X n 1; i. e, W is a sequence of edges (Xil I Xi2)1 (Xi2l Xi3)1 ... I (Xik-I I Xik )1 (Xik I Xil ) that visits each point of S(n) at least once and begins and ends at the same point. Even if W visits some points more than once and traverses some edges more than once, W is feasible for the traveling
S(n), (S(n)) < E,CW le
salesman problem on so TSP 'I.
We now construct a particular W on S (n) in the tradition of Karp (1976) and Supowit, Reingold, and Plaisted (1983). In each subcube Qj for which S(n)nQi :A 0, construct an optimal traveling salesman tour Tj of S(n) n Qi. This creates a set of at most m d within-subsquare tours. We then select a point xt from each Ti and let T* be an optimal traveling salesman tour Of JX*1, X2*, X* d}. The closed walk
M
4
W is then formed by visiting subsquares in the order specified by T" visiting all members of subsquare Qi by traversing Ti whenever T* reaches xt.
To assess the length of W, we first note that T* is a TSP tour of m d points,
so by (1.2), E,CT, lel :!~ CdMd-I . This gives
PTSP(n) = TSP( S(n))
< 1: lei
'~EW
Md (2.4)
TSP(s(-) n Qi) + E lei
cET*
M d
< TSp(S(n) n Qi) + CdM d-1.
We now use (2.3) in (2.4) along with the fact that TSp(S(n) n Qi) is at most
PTSP(s(n. i)) scaled by the subcube size 1/m to get
PTSP(n) = Odn (d-l)ld + r(n)
d
< PTSI(s(n,i)) + CdM d-I
i=1 M (2.5)
< Md i)(d-l)ld Md Md-1,
E PdS(n, + - r(s(n, i)) + Cd
M M
where, for all 1 < < Md the value jr(s(n,i))l maXk- I -
Since m is fixed, we cancel Od in (2.5) to find
Md
s(n, 2 )(d-l)ld > mn (d-l)ld + h(n), (2.6)
where h(n) = o(n (d-,)Id) . Dividing by n (d-1)1,1 and letting n --+ oo thus proves half of the lemma. To obtain the other half, just apply H61der's inequality
w p = dl(d - 1) to E' d s(n, 2 )(d-l)ld and use E,d s(n, n to find that
Md -)(d-l)ld (d-l)ld.
Fli.1 s(n, Z <,mn
El
5
I
We are now in position to prove Theorem 1. First we recall the-subsequence convergence principle which says that if (ak) is any sequence of real numbers with the property that for any integers nj < n2 < ... < nk < ... there is a further
subsequence ni < n' < ... < n' < ... such that aw --+ a as k --+ oo, then in
1 2 k k
fact one must have ak --+ a as k --+ oo. One easy way to see the validity of this
principle is to note that if ak does not converge to a, then there is some a' =,~ a,
-oo < a' < oo, and some subsequence of (ak) that converges to a'.
Now let (nk) be a given increasing sequence of integers. Since 0 < S(n, i)/n < 1 for all n and i, we can find a subsequence (n') of the (nk) and Md constants k
0 < ai < 1 such that for all 1 < i < m' we have
lim s(n', i)/n = aj. (2.7)
k-+oo k
Now, since s(n, n, we have from (2.7) that
M d
ai (2.8)
Similarly, by (2.2) and (2.7), we have
M d
a~d-i)ld M. (2-9)
Now, equation (2.9) and H61der's inequality applied with ui a~d-l)/d and
P
dl(d - 1) give us
M d M d (d-l)ld ( rn d 1d) ild
M a~d-l)/d < aj) (2.10)
(d-l)ld = (d-l)ld
But, by (2.8) we see that equality holds in (2.10), and thus al a2
a (d d I)ld , so applying (2.8) again, we see that ai = 1/Md for all Z'. By the
M
subsequence convergence principle noted after Lemma 1, we therefore have for all
< 4' < Md that s(n, 0/n -+ 1/m d as n --+ co, and the proof is complete.
6
4. Equidistribution in Related Problems
The method just used for the TSP can be applied to the minimum spanning tree, the minimum-length matching, and the rectilinear minimum Steiner tree. If L = L(S) denotes the optimal cost associated with any of these, then we can define
PL(n) = sup scto'll, L(S) and let S( n) be such that L(SL(n)) = p,(n). To show that ISI=n
SL(n) is asymptotically equidistributed boils down to checking that L satisfies two conditions:
1- PL(n) = #L,,n (d-l)ld + o(n (d-1)1d)' whereOL,d> 0 is constant; and
(d-1)1d)' ') n QiJ.
2. PL(n) < m-1 PL(SL(n, i)) + o(n where S L (n, i) SL(
Condition 1 has been proved for the minimum spanning tree, minimum-length matching, and rectilinear Steiner tree problems (cf., Steele and Snyder (1989) and Snyder (1992)), and Condition 2 can be verified for these problems by the method used in the proof of Lemma 1.
For example, if L(S) = MST(S) denotes the total length of a minimum spanning tree of S, we first form a minimum spanning tree MST("'-M('S)Tn Qi) on each
q(-) (d-l)ld
"MSTnQi. These trees can then be interconnected at total cost o(n ) by adding
M' - 1 edges, each costing no more than c/m, where c is constant. This forms a
Q(n) ,(n
~MST. ) n Qi) are no greater than the
heuristic tree on Since the lengths MST("MST
worst-case (within-sub cube) lengths PMST(SMST(n) i))/m, Condition 2 follows.
Checking these conditions for each of the problems yields the following.
Theorem 2. If I S'(n) : 1 < n < oo I is a sequence of worst-case point sets for the function L, where L is the minimum spanning tree, the minimum-length matching, or the rectilinear minimum Steiner tree, then, for any rectangular parallelepiped R C [0, 1]d,
lim SL(n) n R VOld(R) (4.1)
n--+oo n
7
5. Concluding Remarks
The asymptotic equidistribution of worst-case point sets for the problems we have considered offers some support to the conjecture of Supowit, Reingold, and Plaisted (1983) that worst-case point sets are approximated by lattices as n ---~ 00. It is still a major open problem to resolve this conjecture.
Theorem 1 has a rather subtle relationship to some results of Supowit, Reingold, and Plaisted (1983); we explain here how these results relate to ours. In addition to improving current bounds on the constants c2 and c' in (1.2) and (1.3),
2
their analysis of the worst-case TSP in R2 decomposed [0,1]2 into M 2 labeled subsquares of side length 1/m, then constructed a heuristic algorithm similar to that of Karp (1976). Supowit, Reingold, and Plaisted noted that the worst-case performance of the heuristic is attained on point sets that are equidistributed, and they used this observation to prove that the leading constant of the worst-case length of their heuristic tour is identical to the worst-case TSP constant #2 in (1.5). This observation does not produce an equidistribution result for worst-case point sets, but it is suggestive of a result like Theorem 1. Still, a rigorous proof of asymptotic equidistribution of a worst-case TSP point set required a much different path.
There are other open problems that are motivated by our results. For the Euclidean Steiner problem, the limit result for Condition 1 in Section 4 has yet to be established. We believe such a result holds, and it would imply that a worstcase point set for the Euclidean Steiner problem is asymptotically equidistributed. It is also likely that the Steiner points in the Euclidean and rectilinear cases are asymptotically equidistributed.
Another problem concerns the greedy matching. Though Condition 1 in Section 4 holds for this problem, the methods we use to verify Condition 2 do not work since they require a minimality condition. Hence, since the greedy matching is not a minimum-length matching, showing equidistribution for a worst-case point set for the greedy matching problem remains an open problem.
8
ACM-SIAM Symposium on Discrete Algorithms, Association Tor Computing Machinery, New York, NY, Society for Industrial and Applied Mathematics, Philadelphia, PA, 462-466.
Steele, J.M. and Snyder, T.L. (1989). "Worst-case growth rates of some classical problems of combinatorial optimization," SIAM J. Computing 18, 278-287.
Supowit, K.J., Reingold, E.M., and Plaisted, D.A. (1983). "The traveling salesman problem and minimum matchings -in the unit square," SIAM J. Comput. 12) 144-156.
10
I
Bibliography
Beardwood, J., Halton, J.H., and Hammersley, J. (1959). "The shortest path through many points," Proceedings of the Cambridge Philosophical Society 55, 299-327.
Few, L. (1955). "The shortest path and the shortest road through n points in a region," Mathematika 2, 141-144.
Goddyn, L. (1990). "Quantizers and the worst-case Euclidean traveling salesman problem," J. Comb. Theory, Series B 50, 65-81.
Hardy, G.H., Littlewood, J.E., and Po'lya, G. (1964). Inequalities, Cambridge University Press.
Karloff, H.J. (1989). "How long can a Euclidean traveling salesman tour be?" SIAM J. Disc. Math. 2, 91-99.
Karp, R.M. (1976). "The probabilistic analysis of some combinatorial search algorithms '77 in Algorithms and Complexity: New Directions and Recent Results, J.F. Traub, ed., Academic Press, New York, 1-19.
Moran, S. (1984). "On the length of optimal TSP circuits in sets of bounded diameter," J. Comb. Theory, Series B 37, 113-141.
Snyder, T.L. (1992). "Worst-case minimal rectilinear Steiner trees in all dimensions," Discrete & Comp. Geom. 8, 73-92.
Snyder, T.L. and Steele, J.M. (1993). "Equidistribution of point sets for the traveling salesman and related problems," Proceedings of the Fourth Annual
9