Please see PDF version
SIAM J. COMPU7. 1989 Society for Industrial and Applied Mathematics
Vol. 18, No. 2, pp. 278 287, April 1989 007
WORST CASE GROWTH RATES OF SOME CLASSICAL
PROBLEMS OF COMBINATORIAL OPTIMIZATION*
J. MICHAEL STEELEt AND TIMOTHY LAW SNYDER*.
Abstract. A method is presented for determining the asymptotic worst case behavior of quantities like the length of the minimal spanning tree or the length of an optimal traveling salesman tour of n points in the unit d cube. In each of these classical problems, the worst case lengths are proved to have the exact asymptotic growth rate of Pi,,1" ` )/d as n oo, where P is a positive constant depending on the problem and the dimension. These results complement known results on the growth rates for the analogous quantities under probabilistic assumptions on the points, but the results given here are free of any probabilistic hypotheses.
Key words. asymptotics, traveling salesman problem, minimal spanning, tree, Beardwood Halton~ Hammersley theorem
AMS(MOS) subject classifications. 05C35, 901310, 90C10, 52A40
1. Introduction. The purpose of this paper is to illustrate a general method for determining the asymptotic behavior of some classical quantities of operations research and combinatorial optimization. For specificity, we focus on the traveling salesman problem and on the minimal spanning tree of n points in the unit d cube, but the general applicability of our method to a number of other problems will be made evident.
To set our problem precisely, we first note that a Euclidean minimal spanning tree or a traveling salesman tour can be represented by a graph C = (V,, E), where V. denotes a set of n points in [0, 1 ]d, where d ~t 2, and E denotes a subset of the edges of the complete graph on the points of V.. The length of an edge e = {xi, xjl is taken to be the usual Euclidean distance, and we write 1 el = lx, xji for that length. For a collection E of edges we will often use L(E) to denote the sum of the lengths of the edges in E, i.e., we define L(E) = 1 e,~ 1 191. Still, when V is a finite set there will be no ambiguity in using 1 V1 to denote the cardinality of V
The objects of principal interest here are the sequences PIVIST(n) and PTSp(n), defined by
PIVIST(n) ~ max 1 el: T is a spanning tree of Vn
V._[011]"{TTinceT
and
PTSpl(n) = max min E 1 el: T is a tour of V,
V. 10,11`{ T ecT
IV,,1~n
In other words, PMST(n) is equal to the largest possible length of any minimal
spanning tree formed from n points in [0, ]d. Similarly, PTSP(n) is the largest possible
length of any optimal traveling salesman tour through n points in [0, ]d . The use of
max instead of sup in the definitions Of PM1ST(n) and PTSI,(n) is justified by the fact
that the expressions in braces can be viewed as continuous functions on the compact
of [0, ]d, I;f.
set obtained by forming the product of n copies i.e., [0, ]d*
Received by the editors November 30, 1987; accepted for publication June 17, 1988. This research was supported in part by National Science Foundation grant DMS 8414069. t Program in Statistics and Operations Research, Princetorl University, Prineeton, New Jersey 08544. * Department of Computer Science, Georgetown University, Washington, DC 20057.
278
WORST CASE RATES 279
One should note that the functions PIST and PTSp depend on the dimension d. This fact also applies to all of the other functions and constants that are used here. Since d 2 is fixed, we will suppress the dependence Of PMST, PTSP, and other functions on d, but the reader should be mindful of this dependence, especially in the main result.
THEOREm. There are constants 0MST and JOTSp depending on the dimension d 2
such that
(1. 1) PMST(n) OMSTn
and
(1.2) PTSp(n) t6TSpn (d l)ld
as n with,8TSP ~!,8MST 1.
This result provides the determination of the exact asymptotic order of the functions PMST and PTSP in any dimension d ~~t 2. Considerable earlier eflort focused on bounds for PM1T(n) and PTSp(n), but none of the inequalities provided by that work is tight enough to determine that PMST(n) or PTSp(n) are actually asymptotic to a
(d llld
constant times n . Some earlier results of particular interest are the bound of Verblunsky (1951), which says that in d =2 one has PTSp(n):5 (2.8n )1/2 + 3.15, and the bounds of Fejes T6th (1940), which say that PTSp(n) and pMST(n) are both at least as large as (1 e)(4/3) 1/4 n 1/2 for all n:~> N(E). Few (1955) improved the upper bound of Verblunsky (1951) to PTSp(n):_5(2n )1/2+ 1.75 in d= 2 and obtained PTSp(n):_5 d{2(d _ 1)}(I d)12d n (d l)ld + 0(n 1 2/d ) for general d 2.
Recent results have improved these bounds. Few's bound on PTSp(n) in dimension two is sharpened in Supowit, Reingold, and Plaisted (1983), to show that PTSp(n)
114 1/2
(4/ 3) n ' for all n ~> 1. Moran (1984) used inequalities on sphere packing to obtain essential improvements on the upper bounds of Few for large values of d. Goldstein and Reingold (1988) carefully analyze Few's heuristic algorithm to improve the upper bounds in dimensions 3:_5 d ~ 7. They also improve lower bounds, using the exact densities of sphere packings for 2:_5 d :_5 8. Goldstein (personal communication) has further improved the upper bounds in dimensions three and four.
The (2n) 1/2 barrier on PTSp(n) in dimension two is broken by bounds of Karloff
(1987) that show PTSp(n) < 0.984(2n) 1/2+ 11. Also, for low dimensions d = :t 3, Goddyn
(1988) improves all known upper bounds on PTSp(n) by considering an infinite number
of translations of quantizers other than cubical cylinders. / / der which
Some other early work focused on the probabilistic circumstances un one can provide bounds for the lengths of the minimal spanning tree or optimal traveling salesman tour. For example, Ghosh (1949) sharpened earlier results of Mahalanobis (1940) and Jessen (1942) to establish that the expected length of an optimal traveling salesman tour of n points chosen at random from the unit square was at most 1.27n' /2 + 0(1). The bound of Marks (1948) complements the upper bound of Ghosh (1949) by providing a lower bound of (n 1/2 _ 1In 1/2) /2 on the expected length of an optimal traveling salesman tour in d = 2.
The culminating result on the length of an optimal traveling salesman tour under probabilistic assumptions was provided by Beardwood, Halton, and Hammersley (1959). That work showed that if T,, denotes the length of an optimal traveling salesman tour of Xi, where 1: 5 i: 5 n and the Xi are bounded independent identically distributed random vectors in Rd, then with probability one we have the asymptotic relation
(1.3) Tn cdn (d l)ld L f(X) (d 1M d dX.
280 J. MICHAEL STEELE AND TIMOTHY LAW SNYDER
Here, f denotes the density of the absolutely continuous part of the distribution of the Xi, and Cd is a constant depending only on the dimension.
In addition to providing improved upper and lower bounds on the constant cd, Beardwood, Halton, and Hammersley (1959) also indicated that a result analogous to (1.3) holds for the minimal spanning tree. A review of the probability theory which has grown out of the Beardwood, Halton, and Hammersley theorem is given in Steele (1987), and a review oriented toward algorithmic applications is given in Karp and Steele (1985).
The focus of the present work is on the growth rates of the worst case lengths of the traveling salesman tour and minimal spanning tree. There are no probabilistic assumptions used here, and it is perhaps remarkable that one obtains asymptotics that are so close in form to the probabilistic results. Another intriguing aspect of these limit theorems is that the same method applies both to a computationally difficult problem (the TSP) and to one which is computationally easy (the MST).
The proof of the main theorem is given in three sections. The first of these sections provides a general lemma that isolates inequalities that are sufficient to determine the asymptotic behavior Of PMST and PTSP. The following section focuses on minimal spanning trees, and, in particular, it provides an approximate recursion relation for PMST. The construction used to study PTSP in ~ 4 is much like that used for PMST; SO the analysis required for the optimal traveling salesman tour is quite brief.
The final section points out some limitations of this method and comments on some open problems.
2. Asymptotics from an approximate recursion. One principle underlying our asymptotic analysis is that both PMST(n) and PTSp(n) satisfy inequalities which bound their rates of growth and express an approximate recursiveness. The following lemma shows that a slow incremental rate of growth (as expressed by (2.1(i))) and an approximate recursiveness (as expressed by (2. 1 (ii))) are together sufficient to determine the exact asymptotic behavior of a sequence. Even though the lemma appears technical, we will later see that the two required conditions are quite natural to the objects under study.
LEMMA2.1. Ifp(l) = 0 and there is a constant cl i ~!: 0 such thatforallm i ~!t 1 andk ~ i. 1
(i) p(n+l): 5p(n)+c,n Ild
(2.1) and
Md _Md 1 (d 1 'I"r(k) :5 P(Md k),
p(k) k
where r(k) 0 as k oo, then as n > oo p (n) ,8n (d i)ld
for a constant 6.
Proof. From the hypothesis (2.1 (i)) and the fact that p (1) 0 we first note that for 1 ~ i
j 1
p(j) p(i)= 1 {p(k+l) p(k)}
k=l
(2.2) j 1
<,cl X 11d dx 5 el(j(d l)ld _ i(d l)ld).
(d l)ld
Letting i = 1 and j = n in (2.2) shows that p (n) 5 cl n ' so if we define op(k)
p(k)lk Id l)ld . then we see that 0(k) < 5 c, for all k. We can then introduce a candidate
WORST CASE RATES 281
for our limit by
(2.3) y = lim sup oo.
k, _~
Inequality (2.1(ii)) tells us that for all k and m,
(2.4) 0(k) r(k): 5 (p(Md k),
so, given any fixed s > 0, we can choose a k, such that y e :_5 tp(k,) and r(k,) :~5 e,
thus obtaining from (2.4) that
(2.5) 2 e ~ 0 (m d k.)
for all m ~ : 1.
Next define j. = m"k, and consider n such that j. :_5 n_:5j.,j. To bound the absolute difference 10 (n) 0 (j~) 1, we use (2.2): sup 1 p (n) p (j.) 5 C,(j(d ~)ld .(d l)ld) m+1 J.
(2.6) j (d 1)1dMd l[(1 + 1IM)d 1
5 c, k p or, in terms of 0, the binomial expansion gives
(2.7) sup 1 ip (n) 41 (j~) 1 :_5 5 c, {(1 + 1IM)d 1 1} < 5 c, m _'2 d 1.
j :9 n ~~j,,, + 1
From (2.7) and (2.5) we find for j,, :_5 n j,,, that
2 5 c, m _'2 d 1 tP(n),
and, hence, y 2a: 5 lira inf, . 0(n). By the arbitrariness of s > 0, we have proved
lim sup 0(n):_5 lim inf tp(n)
n o n w
and the lemma is complete.
3. Minimal spanning trees. We will now show that PMST satisfies the hypotheses of the preceding lemma. The key issue is the derivation of an inequality like (2.1(ii)). This will be done by a recursive construction of a point set for which a minimal spanning tree has near maximal length.
Q= [0, 1]d Md 1:5 i Md
We first divide the d cube into cells Q, where and each
cell has side length 11m. The boundaries aQi of the cells Qi create a natural grating
in the unit d cube which we denote by LI, i.e., we set H U iti 1 &Q. For 0let H' denote the set of points of [0, 1]d which are within a/2 of H, thus H' is the
grating H fattened to a width of a. Similarly, we define subcells Q'i of Qi by Q't
Qi Ha.
Inside each of the Q'i we now place a set Si of k points for which the length of the minimal spanning tree is (M~'_a)PIVIST(k), i.e., inside each subcell we place a copy of a set of k points that attains the worst case bound on the length of a minimal spanning tree of k points. The factor of (m~ a) equals the side length of Q~,', and it reflects the scaling Of PMST(k) down to the smaller cube. Next, we let T be a minimal spanning tree of the set of m "k points U Si, and we let Ti denote a minimal spanning tree of Si. We will now develop a relationship between L(T) and L(U im=", Ti) that moves us toward an inequality like (2.1(ii)) for PMST.
282 J. MICHAEL STEELE AND TIMOTHY LAW SNYDER
First consider the forest that is obtained from T by deleting from T all the edges that have length as great as a. We let A (a) denote the number of edges deleted from T, i.e., we set
A(a) = l~e E: T:
Since T was connected, the graph that remains following the deletion of A(a) edges has at most A (a) + 1 connected components. Moreover, each of these connected components is contained entirely in some subcell Qi'.
Next, if two or more connected components of T coexist in the same subcell Q'j, then we join them together to make a tree on the point set Si. Since, within any given cell, we can rejoin any two components at a cost not exceeding d'l'm ', the total cost of rejoining all the within cell components is bounded by d 112M 1 A ( a ).
So far we have constructed a spanning tree for each Si, where 1:5 i:s Md. Since the length of each of these trees must be at least as great as the length of the minimal spanning tree T, of the point set Si, we have the bound
md
1 L(T)s L(T)+d'I'm_'A(a). i=l
But we know L(T) = (m ' a)p,s,(k) and L(T) PMST(rndk), so we can rewrite this bound to provide
(3.1) m d(M 1 a)PMST(k) d 1/2M 'A (a) 25 PM1T( Md k).
In order to extract an equality like (2.1(ii)) for PMST from (3.1), we need some elementary facts about sets of points in [0, 11d and their associated minimal spanning trees. We begin by recalling an easy pigeonhole argument, which says that from any set of n points in [0, 1]d, one can always find a pair that are close together.
LEMMA 3.1. There exists a constant C2 such thatfor any {Xl, X2, Xn }_ [0, 1]d,
where n; ! > 2, one has
IXi Xjj: 5 C2n 11d
for some xi and xj, 1 S i Proof. Cover each xi with a ball of radius r centered at xi, and note that such a ball has volume 60dr d' where Wd is the volume of the unit d ball. If all of the balls constructed in this way were non intersecting, then each would cover at least 2 d 'wd r d of [0, 11d , even if we generously assume that each of the balls were centered exactly in a corner of the hypercube. In total, the n balls would cover at least a volume of 2 d 1 Wdr d n, and since [0, 11d has unit volume, we have. 2 d 'wd r d n: 5 1. The lemma is therefore established with C2 = 2 (2d+l)/deo d 11d
One can easily improve the constant C2, but this simply derived constant is sufficient for our purposes. It is now easy to give a bound on PkIST that shows the validity of the first hypothesis of Lemma 2.1.
LEMMA 3.2. There exists a constant C3 such thatfor all n ~ 1, one has the bound
/ d
(3.2) PMST(n + W 5 PMST(n) + C3n 1 .
Proof Let S = {X,, X2, ' ' * 5 Xn+l} denote a set of n + 1 points in [0, 1]d for which the length of a minimal spanning tree is PMST(n + 1). By Lemma 3.1, there exist xi and xj in S such that iXi Xi 1 .5 CAn + I) 11d _= C2n 11d. We form a minimal spanning tree T
Of {Xl, X2, Xi 1, Xi+1 x.+,} and then augment the tree by adding to it the edge
WORST CASE RATES 283
{x,, x,}. This construction provides a spanning tree of S at a cost of no more than L(T) + C2n' 1d . Therefore, we have
ild
PMST(n + L(T) + C2n PMST(n) + C2n
which proves our lemma with C3 = C2.
Naturally we can sum inequality (3.2) to provide a bound on PMST(n).
COROLLARY. There is a constant c, such that for all n _~ 1, one has the bound
(d l)ld
(3.3) PMST(n) l ~ C4n
Here we note that C4 = 2C3 is a sufficient choice for the constant C4.
The next lemma provides a tool for understanding how a minimal spanning tree changes as edges are added or deleted. While the result is reasonably intuitive and can be established by modification of Kruskal's algorithm (see, e.g., Aho, Hopcroft, and Ullman (1974)), the rigorous justification of the modified Kruskal algorithm does not seem to be as easy as the characterization based proof used here.
LEMMA 3.3. Let E be a subset of a minimal spanning tree of S
{Xl, X2, * * * , Xn }_ [0, 1]d , and let S' be the set of points incident with the edges of E. Then, there exists a minimal spanning tree of S' that contains E.
Proof The graph corresponding to the set E consists of k connected components (S1, TI), (S2, T2), . . , (Sk, Tk), where 1 k 1 E 1. We first show that for all 1 i 25 k, Ti is a minimal spanning tree of Si. To see this, consider a minimal spanning tree T. If we form a forest of two trees by removing an edge from T, then it is trivial to note that each resulting tree is a minimal spanning tree of the respective set of points incident with it. Now let T be a minimal spanning tree of S, and recursively apply this fact by removing from the tree T all the edges of T E. As each edge e E: T E is removed, the minimal spanning tree to which e belongs becomes two minimal spanning trees. After removing all the edges of T E, the result is the edge set E, which is a forest of minimal spanning trees.
We first recall a well known fundamental property of minimal spanning trees. If
V, , EJ, ( V2, E2), Vk, EM, where k > 1, is a forest spanning the point set S,
and e = {xi, xj} is an edge of minimum length such that e has exactly one endpoint in
V,, then there exists a tree T* spanning S and including U Ei U {e} such that
U k
L(T*) = min {L(T): T is a tree spanning S and j., Ei c: T}. We use this easily proved fact (see Aho, Hopcroft, and Ullman (1974), or Papadimitriou and Steiglitz (1982)) to construct from the edge set E a minimal spanning tree of Y.
Begin with the edges of E, which constitute a forest of minimal spanning trees, and iteratively add to T, an edge of minimal length over all those edges having exactly one endpoint in S, Merging components this way, we obtain a tree T that spans Y. Moreover, T is a minimum cost tree over all trees that span S' and contain E. Hence, the only way we could lessen the cost of T would be lessen the cost of a tree Ti, where 1 :5 i ~ k_ But, since Ti is a minimal spanning tree, this is impossible, and we conclude that T is a minimal spanning tree of Y. Since T contains E, the proof is complete.
We now use Lemma 3.3 and the corollary to Lemma 3.2 to bound the total length of any k edges of a minimal spanning tree.
LEMMA 3.4. There is a constant c, such that if E is any subset of the edges of a minimal spanning tree Of {Xl, X2, ' . * ' X. }C [0, 11d, then
L(E):_5 c,J E Ild 111d.
Proof Let S be the set of endpoints of the edges of E and note ISI: 521El. By Lemma 3.3, there exists a minimal spanning tree of S that contains E. By inequality
284 J. MICHAEL STEELE AND TIMOTHY LAW SNYDER
(3.3) we have therefore that
1 ~e~: SC41 SIld 111d,
CEE
so the lemma is proved with c, = 2 'd 111d C4.
We require one more general inequality in order to bound A (a) in our key relation (3.1). Formally, we let PMST(X) denote the maximal value k such that there exists a minimal spanning tree of some V, = {Xl, X2, X"}_ [0, 1 ]d with k edges greater than or equal to x in length.
LEMMA 3.5. There is a constant C6 such that for all x > 0, one has
(3.4) 7'MST(X):_5 C6X_ d.
Proof. Let T be a minimal spanning tree Of {X,, X2, xJ, and set 0 r(x)
i{e EE T: lel xfl. By Lemma 3.4 any set Of OT(x) edges of T must have length bounded
111d
by C10TW(' so
1)1d
(3.5) xo r(x) t~i 1 iei t5C5lei~tx
Clearing OT to the left side gives
OT(X)_:5 Cs'X_',
and, since this bound holds for all minimal spanning trees T, the lemma is proved
C6 = ed
with 5 1
Returning to our basic recurrence relation (3.1), we can write it in a form closer to the hypothesis of Lemma 2.1 as follows:
(3.6) m d 1 PMST(k) {m d apMST(k) + d 112M 1 A (C,)} :_5 PMST( Md k).
,d l,ld d
By Lemma 3.2 and its corollary PM5T(k):5 c,k , and by Lemma 3.5 A (a): 5 C6a
so the bracketed expression of inequality (3.6) is majorized by
C4arn d k (d l)ld + C6d 1/2M IC, d.
i d)ld(d+l)
This quantity is approximately minimized by choosing a = m lk( ' and mak
ing that choice proves that there is a constant C7 such that the inequality
d 1 d (d 1)/ (d + 1) ~ d
(3.7) m PMST(k) C7M 1k = PMST(M k)
holds for all m ~~t 1 and k ~t 1. This last inequality shows that the main hypothesis of
1 d)ld(d+l)
Lemma 2.1 is valid with r(k) = C7k( Since we already know that PMST(n + 1) 5
1d
PMST(n) + C3n 1 ' we have verified all of the hypotheses of Lemma 2.1. We have therefore proved that PMST(n) OMSTn (d l)ld as n 00 for all d 2.
To see that PMST~ t 1, we just note that one can place n points in the unit d cube
1d
in such a way that no two are closer together than n ' . This proves that PMSTk_ 1, since any connected tree has n 1 edges.
4. The traveling salesman problem. Just as in the treatment of minimal spanning trees, the central task is to prove the validity of (2.1(ii)). For the traveling salesman problem the task actually turns out to be easier than it was for minimal spanning trees.
As before, we partition [0, ]d into Md cells Qi of edge length m`. We then obtain a fattened grating H' of width a, where 0 < a < m ', and define corresponding subcells Q'i with edge length m 1 a. Into each subcell Q'i we insert a set Si of k points having an optimal traveling salesman tour with length PTSp(k)(m ` a), i.e., the set Si attains the maximal length of any set of k points in a cube of edge length m ' a.
WORST CASE RATES
285
Now, for each 1:5 i:S M d'
we let Ti denote an optimal traveling salesman tour of Si, ~nd we further let T be an optimal traveling salesman tour of the Md k points of UM ,
j, Si. We need to establish a relationship between the total lengths of the two sets of edges T and U i' "1 Ti
To build a heuristic tour T,! through Si, we start by taking the set Ti to be Ei, the set of all of the edges of T that are completely contained in Q~'. If this set of edges forms a graph Gi = (Si, Ei) with ki connected components, then there is a set Cj of at least ki vertices that are in different components of Gi and have degree one or zero. The case of degree zero occurs exactly for those components consisting of a single vertex.
Since Cj has cardinality at least ki, we can apply Lemma 3.1 to find a pair of vertices in Q that are separated by a distance of at most c,ki 11d (m ' a). We now add the edge determined by this pair of vertices to Ti. Repeating this construction, we can add a total of ki 1 edges to Ei and obtain a path T,~ throu gh all of the vertices in Si. The ends of this path can now be joined by one final edge in order to complete the heuristic tour T,~.
This process shows that the length of Ti' is bounded by
ki
(4.1) L( T'j) :_5 L(Ei) + C2 E 1 ._ 11d M 1
j~1
Now, since P rsPM(m` a): 5 L(T,~) and L(EJ: 5 L(T):_5 PTSP(M d k), we can sum
(4. 1) over 1 m d and obtain
'd ki
d Md y j l,d.
(4.2) m PT5p(k)(m ' a): SPTSP( k)+C2M
Next, let A (a) denote the number of edges of T that intersect H'. The number of
f ~d
connected components of U Gi equals ki A (a); so, estimating the inner sum
Ik~ ' j 11d + ki 11d ~d llld
of (4.2) by X dx 5 2ki and then applying H61ders inequality,
we have
M"
d d ~d l)ld
M PTSp(k)(m )~ SPTSP(M k)+2C2M )7 ki
Md d ki) (d l)ld
PTSP( k) + 2C2M 1
j~ 1
PTSP(M d k) + 2 C2 A (a) (' "/'.
This inequality will now be put in the form needed to verify (2.1(ii)). The only real issue which remains is that of bounding A(a), but some intermediate facts are required. First, we note that we can show
(4.4)
PTSP(n + 1)55 p,l,s,(n)+ cn 'ld
by taking n + 1 points 5 such that PTSP07 + 1) is the length of the shortest tour through S and then using Lemma 3.1 to exhibit a heuristic tour through S with cost bounded by PTS,(n)+2C271' 1d, so we have inequality (4.4) with C8 = 2C2. (For examples of this type of argument, where more attention is given to obtaining good values for the associated constants, one can consult Moran (1984). For an easier, but less quantitative, version one can consult Few (1955).)
One immediate consequence of (4.4) is that by summing over l: 5 i: 5 n, we have
(4.5)
where cg = 2 c8.
(d l)ld
PTSp(n) I cgn
1
286 J. MICHAEL STEELE AND TIMOTHY LAW SNYDER
Now, for an edge of T to intersect H', it must have endpoints in two different
Q'i and therefore have length at least a. This gives the bound
(4.6) aA(a)S 1 lel:5PTSI( Md k) :5 C'Md 'k Id l)ld.
lel ~
ecT
When we apply (4.5) and (4.6) to (4.3) we have
(4.7) Md 'PTS,(k):_5 PTSP( Md k) + am "cgk (d 1)ld + C~oa (d I)IdM(d i)21d k( d 1)2/d2
(d l)ld. 1k( 1 d)ld(2d 1) < 1, we see that (4.7)
where c10 ~ 2C2C9 If we now choose a = m m
simplifies to give
(4.8) m d 1 PTSp(k):_5 PTSP(Mdk) +ClIMd 1k 2(d 1)2/d(2d 1),
for a constant cl,.
From inequality (4.8) we see that the main hypothesis of Lemma 2.1 is justified
1 d)ld(2d 1)
with r(k) = cl, k( . Since (4.4) verifies the first hypothesis of Lemma 2.1, we have completed the proof that PTSp(n) OTSpn (d l)ld as n ~. oo. Naturally, since the minimal spanning tree problem is a relaxation of the traveling salesman problem, we have OMST: 5 OTSP.
5. Summary and concluding remarks. The two classical examples that were studied here follow a general pattern that can be used for other problems. One pursues the following recipe: (1) divide the unit d cube into Md subcells of equal size that are separated by a fattened grating; (2) fill the ith subcell with Si, a set of k points on which the geometric object being analyzed attains its worst case length in the subcell; (3) construct a graph C that is associated with the points U tT="I Si c [0, 1] d ; (4) delete all edges of G that are long enough to span the fattened grating; (5) in each subcell, add edges to what remains following the deletion to form a heuristic graph Gi on Si; (6) derive from this construction a recursion involving the length of a worst case edge set; and (7) show that the recursion justifies (2.1(ii)) of Lemma 2.1. Of course, we must also show that the worst case length satisfies (2.1(i)) of Lemma 2.1 to guarantee the result, although proving that the second recursion of Lemma 2.1 is satisfied is usually the task of greater difficulty.
This recipe would be unacceptably vague in the absence of explicit examples, but, be referring to the detailed treatment of the MST and TSP, the application of this technique to other problems should be reasonably straightforward.
The fact that the traveling salesman problem is computationally difficult and the minimal spanning tree problem is computationally easy serves to show that computational complexity is not at the heart of the technique used here. This intriguing circumstance provided one of our motivations for illustrating our technique with these particular problems. A second motivation came from the heuristic algorithms developed by Held and Karp (1970), (1971) which are driven by the observation that the minimal spanning tree problem is a relaxation of the traveling salesman problem.
Limit results like those given here seem to provoke two inevitable questions. The first question concerns the determination of the constants OMST and PTSP (for each d i ~t 2), and the second concerns the possibility of providing convergence rates more precise than p (n) =,Bn (d l)ld +o(n (d l)ld ). The experience of trying to deal with the analogous questions under probabilistic assumptions leaves us with little hope for progress on these points. In particular, one should note that to sharpen the results of Moran (1984) to give the exact value Of PTSP would seem to require new geometric insights into the traveling salesman problem as well as improvements on the best
WORST CASE RATES 287
available results on sphere packing. These steps would be major advances in their own right. Perhaps the problem of improving the error term in our limit theorem to something
sharper than. o(n (d l)ld ) would be easier than determining P; but, still, one would
have to develop a technique that would be completely different than that given here.
REFERENCES
A. V. AHO,J. E. HOPCROFT,ANDJ. D. ULLMAN (1974), TheDesign and Analysis of Computer Algorithms, Addison Wesley, Reading, MA.
J. BEARDWOOD, J. H. HALTON, AND J. M. HAMMERSLEY (1959), lheshortestpath through manypoints, Proc. Cambridge Philos. Soc., 55, pp. 299 327.
L. T. FE.IES 7f6TH (1940), Uber einen geometrischen Satz, Math. L, 46, pp. 83 85.
L. FEW(1955), The shortest path and the shortest road through npointsina region, Mathematika, 2, pp. 141 144.
H. W. CHOSH (1949), Expected travel among random points, Bull. Calcutta Statist. Assoc., 2, pp. 83 87.
L. GODDYN (1988), Quantizers and the worst case Euclidean traveling salesman problem, J. Combin. Theory, Series B, submitted.
A. S. GOLDSTEIN (1988), personal communication.
A. S. GOLDSTE1 N AND E. M. REINGOLD (1988), Improved bounds on the traveling salesman problem in the unit cube, Tech. Report, Department of Computer Science, University of Illinois at Urbana Champaign, Urbana, IL. .
M. HELD AND R. M. KARP (1970), The traveling salesman problem and minimum spanning trees, Oper. Res., 18, pp. 1138 1162.
(1971), The traveling salesman problem and minimum spanning trees: Part 11, Math. Programming, 1, pp. 6 25.
R. J. JESSEN (1942), Statistical investigation of a sample survey for obtaining farm facts, Bulletin of Iowa State College Agricultural Research Report 304.
H. J. KARLOFF (1987), How long can a Euelidean traveling salesman tour be? Tech. Report, Department of Computer Science, University of Chicago, Chicago, IL.
R. M. KARP AND J. M. STEELE (1985), Probabilistic analysis of heuristics, in The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., John Wiley, New York.
P. C. MAHALANOBIS (1940), A samplesurvey ofthe acreage underjute in Bengal, Sanky5 Ser. B., 4, pp. 511 531.
E. S. MARKS (1948), A lower boundfor the expected travel among m random points, Arm. Math. Statist., 19, pp. 419 422.
S. MORAN (1984), Oil the length of optimal TSP circuits in sets of bounded diameter, J. Combin. Theory, Series B, 37, pp. 113~141.
C. H. PAPADIMITRIOU AND K. STEIGLITZ (1982), Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, Englewood Cliffs, NJ.
J. M. STEELE (1987), Probabilistic and worst case analyses ofsome problems ofcombinatorial optimization in Euclidean space, Tech. Report, Program in Operations Research and Statistics, Princeton University, Princeton, NJ.
K. J. SUPOWIT, E. M. REINGOLD, AND D. A. PLAISTED (1983), The traveling salesman problem and minimum matchings in the unit square, SIAM J. Comput., 12, pp. 144 156.
S. VERBLUNSKY (1951), Oil the shortest path through a number ofpoints, Proc. Amer. Mat,h. Soc., 2, pp. 904 913.