SIAM J. COMPU7. 1989 Society for Industrial and Applied Mathematics

Vol. 18, No. 2, pp. 278287, April 1989 007

WORSTCASE 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 worstcase 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 dcube. In each of these classical problems, the worstcase 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, BeardwoodHalton~ 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 dcube, 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 DMS8414069. t Program in Statistics and Operations Research, Princetorl University, Prineeton, New Jersey 08544. * Department of Computer Science, Georgetown University, Washington, DC 20057.

278

WORSTCASE 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 (dl)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

(dllld

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 FejesT6th (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)}(Id)12d n (dl)ld + 0(n 12/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 (dl)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 worstcase 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 _Md1 (d1 'I"r(k) :5 P(Md k),

p(k) k

where r(k) 0 as k oo, then as n > oo p (n) ,8n (di)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

j1

p(j)p(i)= 1 {p(k+l)p(k)}

k=l

(2.2) j1

<,cl X 11d dx 5 el(j(dl)ld _ i(dl)ld).

(dl)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 Idl)ld . then we see that 0(k) < 5 c, for all k. We can then introduce a candidate

WORSTCASE 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 .(dl)ld) m+1 J.

(2.6) j (d1)1dMdl[(1 + 1IM)d1

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)d1 1} < 5 c, m _'2 d1.

j :9 n ~~j,,, + 1

From (2.7) and (2.5) we find for j,, :_5 n j,,, that

2 5 c, m _'2 d1 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)

no nw

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 dcube 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 dcube 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 worstcase 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 withincell components is bounded by d 112M1 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)sL(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(M1 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

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 + W5 PMST(n) + C3n1 .

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, Xi1, Xi+1 x.+,} and then augment the tree by adding to it the edge

WORSTCASE 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

(dl)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 characterizationbased 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 wellknown 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 minimumcost 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 Ild111d.

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 SIld111d,

CEE

so the lemma is proved with c, = 2 'd111d 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 0r(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) xor(x)t~i 1 ieit5C5

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 d1 PMST(k) {m d apMST(k) + d 112M 1 A (C,)} :_5 PMST( Md k).

,dl,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 (dl)ld + C6d 1/2MIC,d.

id)ld(d+l)

This quantity is approximately minimized by choosing a = mlk( ' and mak

ing that choice proves that there is a constant C7 such that the inequality

d1 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

1d)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 (dl)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 dcube

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.

WORSTCASE 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 PrsPM(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 jl,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~ ' j11d + ki 11d ~dllld

of (4.2) by X dx 5 2ki and then applying H61ders inequality,

we have

M"

d d ~dl)ld

M PTSp(k)(m )~SPTSP(M k)+2C2M )7 ki

Md d ki) (dl)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.

(dl)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 Idl)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 (d1)ld + C~oa(dI)IdM(di)21d k( d1)2/d2

(dl)ld. 1k( 1d)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 d1 PTSp(k):_5 PTSP(Mdk) +ClIMd 1k 2(d1)2/d(2d1),

for a constant cl,.

From inequality (4.8) we see that the main hypothesis of Lemma 2.1 is justified

1 d)ld(2d1)

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 (dl)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 dcube 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 worstcase 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 worstcase edge set; and (7) show that the recursion justifies (2.1(ii)) of Lemma 2.1. Of course, we must also show that the worstcase 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 (dl)ld +o(n (dl)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

WORSTCASE 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 (dl)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, AddisonWesley, Reading, MA.

J. BEARDWOOD, J. H. HALTON, AND J. M. HAMMERSLEY (1959), lheshortestpath through manypoints, Proc. Cambridge Philos. Soc., 55, pp. 299327.

L. T. FE.IES7f6TH (1940), Uber einen geometrischen Satz, Math. L, 46, pp. 8385.

L. FEW(1955), The shortest path and the shortest road through npointsina region, Mathematika, 2, pp. 141144.

H. W. CHOSH (1949), Expected travel among random points, Bull. Calcutta Statist. Assoc., 2, pp. 8387.

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 UrbanaChampaign, Urbana, IL. .

M. HELD AND R. M. KARP (1970), The traveling salesman problem and minimum spanning trees, Oper. Res., 18, pp. 11381162.

(1971), The traveling salesman problem and minimum spanning trees: Part 11, Math. Programming, 1, pp. 625.

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

E. S. MARKS (1948), A lower boundfor the expected travel among m random points, Arm. Math. Statist., 19, pp. 419422.

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, PrenticeHall, 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. 144156.

S. VERBLUNSKY (1951), Oil the shortest path through a number ofpoints, Proc. Amer. Mat,h. Soc., 2, pp. 904913.