Please see PDF version
MATHEMATICS OF OPERATIONS RESEARCH Vol. 15, No. 4, November 1990 Printed in U.S.A.
PROBABILISTIC AND WORST CASE ANALYSES OF
CLASSICAL PROBLEMS OF COMBINATORIAL
OPTIMIZATION IN EUCLIDEAN SPACE*'
J. MICHAEL STEELE
The classical problems reviewed are he Iraveling salesman problem, minimal spanning tree, minimal matching, greedy matching, minimal triangulation, and others. Each optimization problem is considered for finite sets of points in Rd, and the feature of principal interest is the value of the associated objective function. Special attention is given to the asymptotic behavior of this value under probabilistic assumptions, but both probabilistic and worst case analyses are surveyed.
1. Introduction. The origin and foundation of the results reviewed here is the 1959 paper by Beardwood, Halton, and Hammersley, "The Shortest Path through Many Points." The importance of that work was made evident in 1976 with the appearance of R. Karp's paper, "The Probabilistic Analysis of Some Combinatorial Search Algorithms." Using the Beardwood Halton Hammersley theorem, Karp showed that, in a probabilistic sense, the computationally difficult traveling salesman problem could be solved efficiently. Karp's work illuminated the power inherent in understanding the asymptotic behavior of combinatorial problems under probabilistic models, and, as a consequence, several research initiatives were set in motion. In particular, motivation presented itself for the investigation of the following questions:
(a) Which aspects of Karp's algorithmic paradigm call for further refinement of the associated probability theory?
(b) Which problems of combinatorial optimization have an asymptotic theory like that revealed by Beardwood, Halton, and HammersIey for the traveling salesman problem (TSPP
(c) Are there features which are more refined than those revealed by the Beardwood, Halton, and Hammersley (BH11) theorem?
(d) Can the proof of the basic 131 111 theorem be usefully simplified?
The main goal of this review is to survey the work which addresses these questions while keeping a close eye on the techniques which seem likely to lead to further progress. In the course of the review, some new proofs and new results are given, but they are pursued only asSar as they serve to illustrate unifying methods.
This review evolves as follows. §2 introduces and motivates the Beardwood, Halton, and Hammersley theorem, then ~3 gives a proof of the most basic form of the BHH theorem and a review of alternative approaches. The fourth section surveys the
*Received January 7, 1988; revised June 26, 1989.
AMS 1980 subject classification. Primary: 68C25. Secondary: 60D05, 60C05, 60K30.
L4OR 1973 subject classification. Main: Combinatorial Analysis. Cross references: Programming: Network ORIMS Index 1978 subject classification. Primary: 011 Analysis of algorithms. Secondary: 490 Networks/ graphs/traveling salesman.
Key words. Probabilistic algorithms, Combinatorial optimization, Traveling salesman problem, Minimal Spanning Tree, Subadditive Euclidean functionals, Minimal matching, Minimal triangulation, K median problem.
~Supported in part by National Science Foundation Grant #DMS 8414069 and #DMS 8812868.
749
0364 765X/90/1504/0749/$01.25
Copyright (0 1990, The institute of management Sciences/Operations Research Society of Arnerica
750 J. MICHAEL STEELE
refinements which can be made in the basic BH1 1 theorem, and the fifth section reviews a generalization of the 131 11 1 with enough power to bring the Steiner tree problem, the TSP, and their rectilinear versions under the same umbrella.
The next four sections focus on problems which have some of the structure of the TSP functional but which fail to be covered by the general results of §5. The problems treated are the minimum spanning tree problem with power weighted edges, the directed traveling salesman problem, the K median problem, the problem of minimal triangulations, and the remarkable two sample matching theorems of Ajtai, Koml6s, and Tusnddy.
§10 takes a turn in perspective and analyzes a nonoptimal process, the greedy matching algorithm. The tools of subadditivity still apply, but in the absence of optimality, subadditivity requires more digging. The whole subject of probabilistic analysis is then put on hold in §11, and the TSP, MST, and matching problems are examined for their worst case performanced. One intriguing aspect of those results is their formal similarity to the probabilistic theorems, despite the absence of any probability model or probabilistic reasoning.
§12 stretches the review's title to embrace the fact that many interesting problems in combinatorial optimization are not Euclidean. There has been some extraordinary recent work on linear programs with random cost, and this work casts new light on minimal spanning trees and the assignment problem which is too good to miss.
Of the new results embedded in this review, it may be useful to note that the proof of the Beardwood, Halton, Hammersley theorem given in §3 seems to be substantially more direct and more elementary than earlier proofs. Also, there is a technical sounding result that has a good story behind it: the sum T,, of the dth power of the edges in any minimal spanning tree of {xl, X21 ... 1 Xj C [0, 11d is bounded uniformly in n. This bound generalizes and simplifies the result which was obtained for d = 2 by Gilbert and Pollak (1968), and it provides a base from which one might expect progress on a probabilistic conjecture of R. Bland discussed in §6. The rest of the story comes from the use of smooth spacefilling curves and of their potential applications in other problems.
2. The BHH theorem. The results considered here always concern finite subsets v = {Xl, X21 .., XJ of points in Rd . These points are viewed as vertices of a graph, any pair of distinct elements of V will be called an edge, and if e = {xi, xj} then lel = Ixi xjl will denote the usual Euclidean length of the line from xi to x,. For the most part, we will be concerned with special classes of graphs such as the class of all tours which can be described (too succinctly) as the set of connected graphs such that each vertex has degree two. The B1 11 1 theorem explains the probabilistic behavior of the functional
L(xl, X2, , Xn) = min E lel
T eE= T
where the minimum is over all tours T with vertex set V. In its most general form one can state the Beardwood, Halton, Hammersley theorem as follows:
THEOREM 1. If Xi are i.i.d. random variables with compact support, then with probability one
(2.1) lim L(Xl, X21 .... Xn)l~(d llld = Cdf f(x) (d Old dx
n Rd
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 751
where Cd > 0 is a constant not depending on the distribution of the X, and where f is the density of the absolutely continuous part of the distribution of the Xi.
We should collect some observations which illustrate the meaning of Theorem 1. First, because the Xi have compact support, the right hand side of (2.1) is always finite. Also, in the case that f is the indicator of a bounded set A, the integral in (2.1)
)11d,
reduces to m(A where m(A) is the Lebesgue measure of A. Finally, part of the content of (2.1) is that if the Xi have compact support which is singular, then L(Xl, X2,..., X,,) is almost surely o(n (d l)ld).
There was a great deal of work on the TSP function L which preceded the BHH theorem. For example, Verblunsky (1951) showed
(2.2) L(x,, X2 ., Xn) < (2.8n)'/' + 3.15
for any (xl, X21 .... Xn } C: [0, lf , and Few (1955) showed
L(xl, X21 ... 1 Xn) < d{2(d 1)}11 11/2'n (d l)ld + 0(n' 21d)
for any {X,,X2. ... 1 Xn) C [0, 1]d . There were also earlier results by Ghosh (1949), Mahalanobis (1940), Jessen (1942), and Marks (1948). The most precise recent result is found in Karloff (1989). More will be said about these results when worst case asymptotics are considered in §11.
In order to appreciate the real thrust of the BHH theorem that it is an exact asymptotic result one should not overlook how easy it is to guess that the appropriate order growth rate of L. is n (d 111d . For example, the n (d l)ld lower bound can be guessed by imagining the Xi to be periodically spaced on the rectangular lattice, and, although such imaginings are purely heuristic, their heart is in the right place. (d 1111
For an upper bound on L,, of order n one can even proceed rigorously and
apply the following elementary lemma:
LEMMA 1. There is a constant c = c(d) > 0 such thatfor n points {x,l X2, .... Xn} [0, lld, there is a pair of points xi and xi such that
1d
(2.3) lxi xjl.< cn 1
No harm is done in omitting the easy proof of Lemma 1 since a substantial generalization will be proved later. Still, the humble bound (2.3) serves us well in many arguments involving sets of points in [0, 1]d , and many of the results surveyed here depend on Lemma 1 in one way or another.
3. Looking for the essence of the BHH. What makes the BHH theorem possible? From Lemma 1 and a naive lower bound based on the expected value of nearest neighbor distances, one is easily lead to conclude that with probability one,
(3.1) 0 < a = liminf Ljn (d J)/ d < limsup Ljn (d I)/ d < 00.
Here, one should note that Hewitt Savage Zero One Law can be used to guarantee that a and 0 are indeed constants. The central insight of Beardwood, Halton, Hammersley (1959) was that tools of subadditivity and self sirnilarity could be brought to bear on L,, with sufficient force to boost elementary bounds like (3.1) to the level of a genuine limit theorem.
There are at least three ways to continue the development of those basic insights. One can refine the original methods in order to give simpler or more intuitive proofs
752
J. MICHAEL STEELE
of the BHH theorem. One can examine the ways in. which the BHH theorem can be sharpened. Or, one can look to abstractions and generalizations of the BHH theorem which might prove fruitful.
To make life easy and to make the method crystal clear, consider Xi which are i.i.d. uniform on [0, 11'. This case is already nontrivial, and it is surely the most often applied. Moreover, the tools for extending from this special case to the case of general distribution with compact support are somewhat removed from the basic geometry of the TSP.
Our first step will be to determine the asymptoties of the expectations (P(n) EL(Xl, X21.... X,) and, in particular, to show
(3.2)
0(n) cCn.
We first divide the unit square [0, 1]' into M2 subsquares of side m ', and we let zi rL l
_k Q~XI<) denote the number of the Xk, 1 < k < n, which occupy the ith subsqUare Qi.
Since Qi has side length m ', we see by scaling that the expected length of the shortest tour through k points in Qi is equal to m 1(p(k). Also, by sewing the M2 subcubes together by passing through them row by row, we can tie any set of subtours of the M2 subsquares of Qi into a grand tour with a total incremental cost bounded by 3m. In terms of expectations this says
m 2 n
(3.3) 0(n) < L F, m '0(k)P(Zi = k) + 3m
i=1 k=0
n n 2k(l m 2)n k
m 1: P(k) (k m + 3m.
k=0
Before taking limits in (3.3) we should verify that (p is decently smooth and does not grow too rapidly. In particular, using Lemma 1 we find constants cl and C2 such that
0(k) < ck 1/2 and0(k + m) < 0(k) + C2rnk 1/2
If we now let n and m go to infinity in such a way that (a) m 2 n converges to A and (b) 0(01n 1/2 tends to its limit superior, the preceding bounds and elementary analysis give us that for each A > 0 we have
(3.4)
limsup 0 (n) In' /2 < A 1/2 EO(W,) + 3A '/',
where W, is a Poisson random variable with mean A. We now choose a subsequence nk such that
lim 0(nJInk' /2 = liminf (p( n) In 1/2.
k ~ n
The shooting is almost over. We just let A = nk in (3.4) and let k go to infinity.
Since the probability mass of W
,, is highly concentrated in the interval A + EA and since (p is well behaved we obtain
lim n 1/2 EO(WJ + 3% 1/2 = liminf(P(n)/n 1/2.
k n
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 753
In view of the main inequality (3.4), we have proved that the limit of 0(n)ln' I' exists. To give more details would spoil the fun, so we count the first step (3.2) as done. The second step is to show that with probability one,
(3.5) lim (L,, ELj In 1/2 = 0,
n m
and we begin with some recent observations of Rhee and Talagrand (1987).
For each 1 < i < n, we let A j denote the sigma field generated by Xj, 1 < i.
Also, we let T' denote the length of the shortest tour through the n points
{Xly X25 5 Xi 1~ Xi+ X, I). Two nice facts about the T' is that E(VIA)
E(P1 A j 1), and, of course, E(P1 A j 1) = E(L,, 1 A j I). So if we let A j = L,, P, we
see
(3.6) di = E(LjAi) E(L,1Ai 1)
= E(L,, PIA) E(Ln V1Ai 1) = E(AilAi).
Now, L,, ELn = F~7= 1 d, and the di are orthogonal random variables (in fact martingale differences), so
n 2 n
'A2 = nEA2
(3.7) Var L,, = E di E(d,~) < E j 1
where, in the last two steps, we first applied Jensen's inequality and then used the fact that Ln is symmetric when viewed as a function of the Xi, 1 < i < n.
We have the simple bound A, < 2 min, From the uniform boundedness of Var L, and Chebyshev's inequality, we have
P(W,, EL,,l > en 1/2 ) < co6 'n ',
and if we let nk be the greatest integer not exceeding k 5/4, then the Borel Cantelli Lemma further tells us L,,,, EL,, with probability one. Also, by applying Lemma 1
repeatedly, we can check that for nk < n < nk 1 , we have
(3.8) L,, < L,,& + C01k + 1 nk) nk 1/2
and for our choice of n,,, inequality (3.8) shows max,,,_, L 1 0 as
,17 , 17,, 1 1 L 17k~
k Moreover, if we first take expectations in (3.8), we have max,,, 1 EL,,
EL,,k > 0 as k oc. Together with the almost sure asymptotic relation L,, EL,,,,
these observations complete the proof of our second step.
This proof differs from earlier proofs of the Beardwood, Halton, Hammersley theorem in several respects, but in particular there is no introduction of a Poisson process to produce independence of the tours within the Qi. Even the simplified proof of the BHH theorem given in Karp and Steele (1985) relied on the traditional Poissonization which has been carried along since 1959.
The Poisson embedding technique has some conceptual advantages over a bareknuckles proof, and probably the main virtue of the present method is that it is honestly easy enough to be given in a beginning graduate course.
754 J. MICHAEL STEELE
One particular benefit of avoiding Poisson embedding and the conditioning argument is that it circumvents the need for an explicit Tauberian theorem. In Hochbaum and Steele (1982) and Karp and Steele (1985), a Tauberian theorem for Borel averages was used to back out of the smoothing introduced by the Poissonization. Such a path provides for some economy of thought, but the covert Tauberian step used here is more elementary and direct. Nevertheless, one is forced to own up to the fact that there was no explicit Tauberian step in the original BHH proof.
This consideration of Poissonization and Tauberian arguments for Boret averages should not leave the impression that such techniques are automatically to be avoided. As Bingharn (1981) shows, there is a powerful armory of results which can be used for backing out of Borel averages. Also, Hartmann (1987) provides Tauberian theorems which are designed specifically for problems like the probabilistic analysis of the TSP.
The martingale argument introduced by Rhee and Talagrand and applied here in a simplified form will probably become the standard approach to the variances and tail behaviors of random variables like L, The application of the inequality of Efron and Stein (1981) by Steele (1981b) provided a simplification and strengthening of earlier methods, but, with all of the machinery of martingales in play, the Efron Stein inequality is not likely to continue to be the tool of choice. Still, one should note that the martingale method and the Efron Stein method are closely related.
To give a brief idea of this relationship we first recall a variant of the Efron Stein inequality from Steele (1986b):
For any function Y = Y(Xl, X2.... 1 Xn) of n independent identically distributed random variables Xi one has
n (Y Y(j))2
Var Y < Y2E L
j=1
where Pi) is identical to Y except X, has been redrawn, i.e. Y(j)
Y(Xl, X21 ... 5 Xi 1, )~il Xi+ 15 .... X,) where the 2n random variables Xi, ~i, 1 < i
< n, are Li.d. It should be evident that for L,, = Y the combinatorial facts one needs to use to provide bounds on Y Pi) are closely related to those used to bound the martingale differences di of (3.6). As final evidence of the closeness of the two approaches to Var L, we should note that, in fact, Rhee and Talagrand (1986) have shown that the Efron Stein inequality can be proved by martingale methods. Other proofs and generalizations of the Efron Stein inequality are provided by Karlin and Rinott (1982), Vitale (1984), and Steele (1986b).
Even at this early point, it may be useful to record a basic open problem. Since VarL,, is bounded for d = 2, it seems inevitable that one has a genuine limit,
(3.9) lim VarL, = a > 0.
n w
So far, the best we know in this direction is the result due to Rhee (1988) that
(3.10) liminf Var L, > 0.
n
A less certain conjecture than (3.9), but one that is still very likely, is that a central limit theorem holds:
(3.11) Ln ELn N(O, a).
As it happens, there is a close relationship between (3.9) and (3.11) through the
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 755
central limit theorem for martingales, and if (3.9) can be established, (3.11) is liable to fall to the same insights. All one needs to add flesh to this speculation is to consider L,, as a sum of martingale differences as in (3.6) and to think through the underpinnings of the martingale central limit theorem as organized by Rootz6n (1983).
4. Refinements of the BE[H. Weide (1978) observed that a number of subtleties lie behind the probabilistic models which motivate methods like Karp's partitioning algorithm for the traveling salesman problem. For example, one can think of problems as being incrementing where {X,, X2,..., Xj grows to {X,, X2,...' Xw Xn+lt or, independent where a problem of size n given by S = {X,, X2,..., Xj is replaced
by a problem of size n + 1 given by S' = {XlI, X2 Xn', 1) where S' is independent
of S. For models of the second type, one needs a notion of convergence which is
stronger than almost sure convergence. Fortunately, the classical notion of complete
convergence seems well suited to the task.
In Steele (1981b) it was proved that for independent random variables Xi with the uniform distribution on [0,112 one has for any 4E > 0 that
(4.1) P(iL,In112 P1 > E) <
In classical terms, (4.1) says that L,In'l' converges completely to
The proof of (4.1) was achieved by combining the inequality of Efron and Stein (1981) with a recursion argument pulled along by H61der's inequality. For d = 2, it was also proved that for all k > 0 there is a constant Ck such that
(4.2) E(L~ _ EL,')k 1< Ck
for all n > 1.
These moment inequalities imply strong bounds on the tail probabilities ML, EL,1 >, t), but still sharper bounds were obtained by Kern (1986), who combined moment generating functions with the Efron Stein inequality. The most general and powerful approach to the tail probability of L,, is the martingale method introduced in Rhee and Talagrand (1987). For the TSP with d = 2, Kern showed there are constants p > 0 and y > 0 such that
(4.3) P(lL,, EL,,l >, t) < P exp( ytIn' /4
while Rhee and Talagrand (1987) showed there is a constant y > 0 such that for
n > 2,
(4.4) P(~L, EL,,~ > t) 2 exp(_ yt2/log n) and
(4.5) P (1 L,, EL,, t) < 2 exp( yt).
By combining the last two inequalities with tools from the interpolation theory of linear operators, Rhee and Talagrand (1989a) further showed there is a 3 > 0 such that
(4.6) P(IL, EL,,l > t) < 2exp(_8t2/log(l + t)).
The inequalities (4.3), (4.4), (4.5), and (4.6) are all much stronger than one needs to
756
J. MICHAEL STEELE
establish the complete convergence (4.1), and they also provide basic improvement on the information available from (4.2),
The final leg in this development was the proof of the full large deviation result of Gaussian type; there is a K > 0 such that for all t >~ 0 we have that
(4.7)
P( 1 L,, EL,, 1 > t ) < K exp ( _ t 2 IK)
This result was established in Rhee and Talagrand (1989b) where the martingale methods were coupled with delicate combinatorial arguments. By considering the interesting "duaV variable
Y, ~ max{k: L(Xi,, Xi,. .. , Xj < s, for all k subsets of Xl, X21 ... 1 XJ 1
Shamir (1989) has provided an alternative approach to the tail behavior of the TSP, but so far the approach falls short of (4.7). The details are a bit too long to trace here, but the key insight is that Azuma's inequality applies more robustly to Y, than to L,, because changing one of the Xi always changes Y, by either 1 or 0.
5. Generalization of the BH11. The first proof of a generalization of the BHFI theorem was given in Steele (1981a), but an important intermediate step was taken in Papadimitriou (1978) where pains were taken to articulate the properties which were central to the original proof of the BHH theorem.
How can one specify a general class of variables for which BHH type results will apply? How might one prove a limit result using only abstract properties of the TSP functional?
We will consider functions L which are defined for all the finite subsets of R d . The properties we require of L are reasonably few, and one can easily check that they hold for the TSP. In particular, we make the following assumptions:
Al. Maxl, aX21 .... ax,) = aL(xl, X2,. Xn) for all real a > 0.
A2. L(xl + X, X2 + X Xn + x) = L(xl, X2.... 1 Xn) for all x EE W. d
Since L is a function on the finite subsets of R ' we also note that L(x,, X2.... 1 X~) is the same as Mx,0), X..(2), * Xo (n)) for any permutation o,: [1, n] [1, n]. The function ' L is also assumed to be monotone, i.e.,
A3. L(x U A) >, L(A) for any x E= R d and finite subset A of W.
If 0 denotes the empty set, we always suppose M4)) = 0 and note that the d
monotonicity of L entails positivity, i.e., L(A) >, 0 for all finite sets A c R
Some boundedness of L is required, and a simple (but excessive) choice is provided by an assumption of finite variance,
A4. Var(L(X,, X21 ... 1 Xn)) < 00 whenever X,, 1 i < n, are independent and uniformly distributed in [0, 1]d.
The preceding assumptions are almost trivial to verify for a large number of problems, and one cannot prove very much using the bare assumptions Al A4. What is needed is a more serious restriction powerful enough to get to the essence of the functionals like the shortest tour length.
We take {Qi: 1 <, i < m d} to be a partition of the d cube [0, 11d into md similar cubes with edges parallel to the axis and let Qi denote the dilated set defined by {x: x = ty, y E= Q}. The subadditivity hypothesis, which is the key to our main result, can be given as follows:
A5. There exists a C > 0, such that for all positive integers m and positive reals t, one has
in d
L({xl, X2, x,,} n [0, t]') 57, L({xl,X21 .... x,,} n tQj + CtMd 1.
1
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 757
Functionals satisfying Al A5 are fortunate indeed, since they satisfy the following generalization of the theorem of Beardwood, Halton and Hammersley.
THEOREM 2. Suppose L is a monotone, Euclidean functional on W' with finite variance which satisfies the subadditivity hypothesis. If (Xi: 1 < i < } are independent and uniformly distributed in [0, lld, then there is a constant 0M such that
lim L(Xl, X2, , XjIn (d l)ld =,8(L)
n oo
with probability one.
The proof of this result is too involved to repeat here. In spirit it rests upon a subsequence and subadditivity argument used earlier in different contexts by Kesten (1973) and Richardson (1973), but of course it also draws on many of the insights of the original proof given by Beardwood, Halton, and Hammersley (1959).
To extend Theorem 2 to random variables which are not uniformly distributed, one must make additional assumptions. We will call L scale bounded provided
A6. There is a constant B such that
L(x,, X21 .... XjItnId 1)1d <~ B for all n >. t, t >, 1, and
{Xl 1 X21 ... 1 Xn} C [0, t 1 d
Also, we call L simply subadditive provided
A7. There is a constant B such that
L(Al U A2) < L(A1) + L(A2) + tB
for any finite subsets A I and A 2 of 101 t Y.
The last assumption we need is upper linearity. A Euelidean function L is called upper linear provided
AS. For any finite collection of cubes Q, 1 < i d < s with edges parallel to the axes
and for any infinite sequence xi, 1. < i < co, in R one has
S S
L({xl, X2 . , x,} n Qi) < L~{xl, X2, XJ n U Qi + o(n(' 1)1d
The set of supplemental conditions is not as tidy as our first set, but eight is enough, and the conditions just laid out suffice to provide a full fledged gelleralization of the Beardwood, Halton and Hammersley Theorem.
Ti iEORr m 3. Suppose L is a Euclidean functional which satisfies assumptions AI A8. There is a constant M(L) such that
lim L(Xl, X2,..., XJIn(d_ 1)1d = S(L) f f(X)ld 111,1 dx a. s.
n . Rd
for any independent identically distributed random variables {Xi} with bounded support in Rd and absolutely continuous part f(x) dx.
Among the functionals to which Theorem 3 can be applied directly are the TSP, the Steiner tree problem, and their rectilinear versions. Notable functionals to which Theorems 2 and 3 fail to apply include the minimal spanning tree (MST) and the
758 J. MICHAEL STEELE
minimal matching problem. Ironically, these problems fail to be covered by Theorem 2 just because they lack the simple monotonicity property A3. For these functionals and several others, the simple failure of A3 causes more trouble than one might have easily imagined.
A generalization of Theorem 3 which relaxes assumption A3 is also given in Steele (1981a), but the minimal matching problem still falls out of its range, despite the comments in Steele 0.981a, pp. 372 373). The easiest way to establish the asymptotic behavior for the minimal matching problem is by direct arguments, and, in fact, many problems which fall just outside the class covered by Theorem 3 end up having enough individual character to justify specialized analysis. A feeling for the range of the techniques which have been built up to deal with such cases can be obtained by examining the results of the next three sections on minimal spanning trees, the directed TSP, the K median problem, and minimal triangulations.
6. Minimum spanning trees and power edge weights. If we let M,, denote the length of the MST of a random sample,
(6.1) M,, = min ~', lel
T eE= T
where the minimum is over all spanning trees of {X,, X2,..., XJ, one would certainly expect a result for M,, like the limit theorem obtained for L, Such a result does not come easily out of the general results summarized in Theorems 2 and 3, even though the classic paper of Beardwood, Halton, Hammersley (1959) already noted that the asymptotics of M,, should follow the same probability law as L,
Curiously, almost everything one knows about discrete optimization suggests that M,, should actually be easier to study than L, After all, Papadimitriou (1977) showed that the task of computing L,, is NP complete, while the computation of M,, is easily achieved by a variety of well known, fast, greedy algorithms. Still, because M,, lacks the basic monotonicity on which Theorem 2 depends, the probability theory of M, is much more troublesome than that of L, Nevertheless, by relying on bare handed understanding of M,, in cooperation with subadditive techniques, one can master the asymptotics of M,, and even more complicated functionals.
Since M,, should be so simple, there is natural inclination to expect results which are more extensive than those obtained for L, One natural step is to consider the more general functional
(6.2) min 1: qi(lel)
T eeT
where qi is a positive, monotone function.
Unlike the functionals considered previously, this functional fails to be homogeneous of order one, i.e. M,,(a) fails to satisfy Al. Despite this and other differences, the asymptotic theory of this M,(,') fulfills our natural expectations, and in Steele (1988) the following result is established:
THEOREm 4. Suppose Xi, 1 < i < oo, are independent random variables with distribution iu with compact support in R', d >, 2. If the monotone function 0 satisfies 0(x) x a as x 0, for some 0 < a < d, then with probability one
(d a)l X)(d a)1d d
(6.3) lim n dMn(a) = c(a, d) X.
n fRJ(
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 759
Here, f denotes the density of the absolutely continuous part of g, and c(a, d) denotes a strictly positive constant which depends only on the power a and the dimension d.
Part of the motivation for Theorem 4 and the more general study of power weighted edges comes from a conjecture of R. Bland, who was led by numerical experimentation to suspect that for Xi i.i.d U[O, 11', one has with probability one that
(6.4) lim min E le ld = C < 00.
n m T eE= T
Although this probabilistic conjecture emerged only recently, some earlier work was already waiting to speak in its behalf. In particular, Gilbert and Pollak (1968) showed by a delicate geometrical argument that in d = 2 the sum Ele 12 is uniformly bounded for any minimal spanning tree and any set {X 11 X21 ... 1 X~ } C [0, lf.
By applying some results on spacefilling curves, it turns out to be easy to prove the result of Gilbert and Pollak and even to extend it to arbitrary dimensions. The key observation is that which says there is a function f from [0, 11 onto [0, 11 d which is Lipschitzian of order 11d, i.e.,
if(X) _f(y)l <
(6.5) ' C1X _ Y111d
for a constant c > 0. This bound holds in fact for several of the classical spacefilling curves, see Milne (1980).
To apply this to the bounding of edge weights of a minimal spanning tree, we suppose V,, = {Xly X2.... 1 Xn} C: [0, 11d and let T be a minimal spanning tree of V, Since f is surjective we can choose points {y11 Y21 . , Y,,} in [0, 11 such that f(y) = xi. Next, we order the yi to give Y(1) < Y(2) < * * * y(,,) and define a new suboptimal spanning tree T,, on V,, by choosing the n 1 edges (f(y(i)), f(y(i , 1))), 1 <, i < n. By the optimality of T and the Lipschitz property of f, we find
" 1
(6.6) le I d le 1 d y7, 1 f( Y(i)) _ f( Y(i ' 1)) d
e E= T e E T,, i=1
n 1
c d y(i) y(i + 1) Cd.
By comparison with the complexity of the proof of Gilbert and Pollak (1968) in d = 2, this proof of the uniform boundedness of Lleld is almost effortless. All of the geometry of [0, 1]d has been compressed into the existence of the Lipschitz spacefilling curve. In the case of d = 2, the technique used above was first discovered by S. Kakutani. The broad usefulness of the spacefilling heuristic has been emphasized in Bartholdi and Platzman (1988). For a review of the oral tradition behind the spacefilling heuristic one should read the comments of Adler (1986). Also, for a discussion of power weighted edges in problems other than the MST, but within the range of Theorem 3, one should consult the recent thesis of Troyon (1988).
Although the main hope concerning the bound (6.6) is that it provides a sensible step toward proving Bland's conjecture, inequality (6.6) has applications in its own right. For example, by applying H61der's inequality to (6.6) one finds that the sum of 1)1d
any k edges of an MST of {X], X2 XJ is bounded by ck(d ' where c is the Lipschitz constant of (6.5). The delicacy of this fact can be appreciated by asking if the analogous fact holds for the TSP. The issue which makes the question subtle is that an optimal tour with respect to edge weights lel can be quite different from an
760 J. MICHAEL STEELE
optimal tour with edge weights le 1d. In contrast, an important fact used in (6.6) is that if a tree T minimizes Le = Tlel then T minimizes E, 1. TO(Iel) where 0 is any monotone increasing function, and in particular, T minimizes E, c 7.1 e Id.
The geometry of Euelidean minimal spanning trees is considerably richer than that of the TSP, and there are several quantities like the number of leaves which have a much different character than the length related quantities which have been discussed so far. Still, it turns out that subadditivity and Efron Stein variance bounding are again effective, and in Steele, Shepp, Eddy (1987) it is proved that with probability one the number of leaves of an MST of an i.i.d. sample with compact support in R2 (but otherwise general distribution) is asymptotic to cn with probability one. While the value of c is not known analytically, simulations suggest that c 0.22 for random variables with the uniform distribution on [0,1]2.
7. The directed TSP. Karp (1977) posed the problem of formulating a probabilistic model of the directed traveling salesman problem WTSP) which supports an asymptotically optimal probabilistic polynomial time algorithm. One such model given in Steele (1986a) also serves to illustrate that the techniques of subadditive Euclidean functionals are sufficiently robust to be able to deal with information which is exogenous to the location of the points.
As usual, we suppose Xi, 1 < i < , are independent random variables with the uniform distribution in the unit square [0,112 , and we take V,, = {Xl, X21 ... 1 XJ as the vertex set for our directed graph G, The edges of the complete graph on V,, are given directions just by flipping coins. Formally, we take independent Bernoulli random variables Yjj, 1 < i < i < n, which are also independent of V,, and for which P(Yij = 1) = 1/2 = PWij = 0). The directed edge set E,, is defined by taking (Xi, Xj) E E,, if Yij = 1 and (Xj, X) c: E,, if Yij = 0.
The random variable of interest here is D, the length in the usual Euelidean distance of the shortest directed path through all of the vertices V,, of G,
It may not be apparent that there is always a directed path through V, but its existence follows from a classic result of R6dei (1934). An algorithmic proof of R6dePs theorem is given in passing in Steele (1986a), but the main results of that paper are the following:
THEOREm 5. There is a constant 0 < < such that as n
(7.1) ED, P Fn .
THEOREm 6. There is a polynomial time algorithm which provides a directed path through V,, with length D,,* which satisfies
(7.2) ED,* < (1 + E) ED,
for all E > 0 and n >, N(E).
The directed traveling salesman problem has only been studied formally in the plane, but it is not hard to show by the same methods that the natural d dimensional analog ED,, 0,n(' ')1' holds for any d >, 2. A more serious issue concerns the possibility of stronger types of convergence. Because of the secondary randomization of the Yij's used to determine the direction of the edges, the almost sure convergence theory for the directed TSP seems substantially trickier than that for the undirected problem. Still, the complete convergence problem for the directed TSP has recently been solved in Talagrand (1989).
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 761
In the course of juxtaposing the limit theory of D,, and its algorithmic theory, it is worth recalling that one does not always need the exact limit theory in order to provide a useful algorithmic theory. This fact is nicely developed in Halton and Terada (1982) where the probabilistic partitioning algorithm for the TSP in R d is given in detail. Finally, one cautionary point is that there is not much in common between the directed TSP just reviewed and the asymmetric TSP considered in Karp (1979) and Karp and Steele (1985).
8. Problems of location and triangulation. The TSP and MST are natural candidates for the development of a refined limit theory because they are among the most studied problems in the area of Euelidean combinatorial optimization. But besides the TSP, MST, and their variants, there are many other functionals of interest and importance. This section discusses two such functionals, the first of which is the k center problem.
2
Given an integer k and any set of n points {Xl, X21 ... 1 Xn} of R ' one defines the
cost of the K center location problem by
n
(8.1) M(k; X 11 X21 ... , xJ = min min 1 xi xj
S: ISI=k PES
For 0 < p < we can also define the more general functional
n
MP(k; x,, X2,..., Xn) = min minIxi xjlp.
S: ISI=k jes
Upper and lower bounds determining the order of magnitude of M were obtained in Fisher and Hochbaum (1980) and Papadimitriou (1981), and the following analog of the BHH theorem for MP was obtained in Hochbaum and Steele (1982).
THEOREM 7. If {Xi} are independent and uniformly distributed on [0,1]2, then for any 1 < p < 2 and 0 < a < 1 we have with probability one that
lim M,,([ an]; X], X2, Xj In 1 p /2 = C,, p
n ~~
.for some constant 0 < c,, p < 00.
This result was obtained by using subadditivity and Tauberian arguments to obtain the asymptotics of EM,, and by using the Efron Stein inequality to bound Var(mp).
The same approach was applied successfully in Steele (1982) to prove a conjecture of Gy6rgy Turdn on the rate of growth of the minimal triangulation of n points independently and uniformly distributed in the unit square.
By a triangulation of a finite set S = {X 1, X21 ' ' , XJ C R2, we mean a decomposition of the square [0,112 into triangles such that each xi E S and each of the square's four corners is a vertex of some triangle. An important technical aspect of this definition is that we do not require that each vertex of the triangulation he an element of S. As one might expect, the length of triangulation is taken to be the sum of the lengths of all the edges in the triangulation, and the quantity central of interest is T(x, X2.... 1 Xn), the minimum length over all possible triangulations.
The main lirnit result for triangulation takes on a familiar cast, but as will be reviewed shortly there are new features of the triangulation problem for which Theorem 8 fails to give a good hint.
1
762 J. MICHAEL STEELE
THEOREM 8. If T, = T(Xl, X21 , X,,) where X, 1 < i < are independent and uniformly distributed in [0,1]2, then
T
lim ' = 8
n vrn
with probability one for some constant 0 > 0.
To dispel any sense that Theorem 8 only presents more business as usual, one should ponder some of the problems that wait in the wings. Can one avoid the Steinerization which was introduced as the technical part of the definition? Also, what is the proper analog of this result in [0, 1]d 9 An interesting aspect of the second question is that the analog of edge lengths of the triangulations in R' is surely the area of the faces of the simplicial decomposition in Rd. This problem leads to the consideration of a discrete probabilistic Plateau problem. Such problems were first posed in Beardwood, Halton, and Harnmersley (1959); but, despite the near 30 year lapse, there has been no progress in dimension d >, 3.
9. Two sample matchings. Growth rates of order n (d I)/d occur so frequently in problems of combinatorial optimization in Euclidean space, one eventually yearns for problems which exhibit different behavior.
Ajtai, Koml6s, and TusnAdy (1984) considered the natural problem of minimal
Euclidean matchings of a pair of random samples for [0,112 , and found a striking new
~n log n behavior. An amusing twist of their discovery is that for d >, 3, the
logarithmic term is no longer present and the habitual n (d l)ld growth rate again
prevails.
In the course of their work, Ajtai, Korn16s, and Tusnfidy also developed two powerful qualitative features of random samples in [0, lf which are intimately related to many optimization problems. But, before describing these features, we should lay out the results for which they were developed. Given Xi, 1 < i < W, and Yi, 1 < i < oo, two independent sequences of random variables with the uniform distribution on [0,112, the random variable of central interest in Ajtai, Korn16s, and Tusnddy (1984) is defined by
n
(9.1) T,, = Min xlr(i) yi
7r
In longhand, T,, is the cost of the minimal bipartite matching between the X's and the Y's. The main theorem of Ajtai, Korn16s, and TusnAdy (1984) sharpened an earlier upper bound of 0P 1/2 log n) due to R. Karp (unpublished) and determined the exact order of T,:
THEOREM 9. There are constants 0 < cl < C2 < such that
(9.2) P(CA 109 n < T, < CA log n 1
as n >
There are two ingenious ideas which underlie the proof of (9.2). First, the proof of the lower bound depends upon the construction of a weight function f (which
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 763
depends upon the X's and Y's) such that f overweights the X's, in the sense that
(9.3) p f( Xi) fl Y) > Lc I ~n log n 1.
The function f is also proved to be Lipschitzian,
(9.4) if(x) f(y) 1 < LIx yL
4r The facts (9.3) and (9.4) instantly justify the lower bound in (9.2), and there are
doubtless other two sample problems where the existence of such an f is a powerful
tool. It also is interesting to see a Lipschitz function crop up again after the
appearance of the deterministic Lip. function which proved so useful in studying
power weighted minimal spanning trees.
The second device developed to prove (9.2) concerns an elegant continuous
analogue to the transportation problem. Risking a little colorful language, suppose
you have a pile of dirt of weight 1In located at each n random points X,, X2,..., X,
in [0,112 . Further, suppose you want to spread that dirt out over a rectangular field
,R , c: [0,112 of area exactly 11n, such that all of Xi's dirt is spread evenly over Xi's
rectangle Ri. The total transportation cost of this redistribution can be measured by
n
SX=
(9.5) n f JXi ul du.
Ri
Here, of course, the rectangles Ri are random pairwise disjoint sets that form a partition of [0, lf. We should note each Ri depends on all of the variables Xi, 1 < i < n, and, also, there is no requirement that Xi E Ri.
The main fact about the variables S' is that the Ri can be constructed so that as n oo we have
(9.6) P (Sx < c~n _log n
Inequality (9.6) speaks directly to the bound sought in (9.2) since
(9.7) T', < Sx + sty,
as one can see by confirming that shipping the X's dirt to [0, l]' and reversing the shipment of the Y's dirt to [0, lf gives a real valued solution to the transportation problem between X and Y. By a classical result of linear optimization, the minimal transportation solution must be a matching, and, therefore, the cost 1l, of the minimal matching has to be less than Sx + Sly,
A final aspect of the two sample matching problem is that it has rich connections to several other problems of interest: bin packing, grid matching, and empirical discrepancies of lower layers. For these connections and many other interesting geometric insights one can rely on Shor (1985), Leighton and Shor (1986), and Coffman and Shor (1989).
10. Greedy matchings. One reason subadditive methods are effective in the probabilistic study of optimization problems is that optimality often provides an almost automatic path to the required subadditivity properties. Such circumstances no longer prevail when one studies asymptotically suboptimal heuristics, and in such cases considerable restructuring of the basic subadditive machinery may be required
764 J. MICHAEL STEELE
before limit results can be obtained. For example, the analysis of the greedy algorithm for minimal matching given in Avis, Davis, and Steele (1988) depended critically upon extracting subadditive inequalities directly from the combinatorial properties of the greedy matching process, even though the eventual result is just as one would expect:
THEOREM 10. For each integer d > 2, there is a positive constant c,, such that if Xl, X21 ..., are i.i.d. random variables with values in R d and bounded support, and if Q, denotes the Euclidean edge weight of the matching attained by the greedy algorithm applied to {Xl I X2, XJ, then with probability one as n
Q, C d n(d I)/ d f 101 dx.
R,,f(X)(d
Here, f is the density with respect to d dimensional Lebesgue measure of the absolutely continuous part of the distribution of the Xi.
One way to appreciate the analysis of the greedy matching problem is to consider heuristics for some closely related problems which still resist analysis. For example, for TSP heuristics based on nearest neighbors, minimal insertions, and many other processes (Karp et al. 1984, Lawler et al. 1985, and Rosenkrantz et al. 1977), one expects a result like Theorem 10. Such results are not yet available, and they are not likely to come easily. In the meanwhile their resistance helps illuminate the distinctive nature of those problems, like the greedy matching problem, where progress has been made.
11. Worst case growth rate results. The worst case behavior of a Euclidean functional is often remarkably parallel to its probabilistic behavior. This fact may come as a surprise, but the TSP and MST provide forceful illustrations.
To spell out the details, we again represent a tree or a tour by a graph G = (V, E), where V,, denotes a set of n points in [0, 11', E denotes a subset of the edges of the complete graph on the points of V, and L(E) denote the sum of the lengths of the edges in E.
Conceptually, the worst case analyses of the TSP and MST are simpler than the probabilistic analysis, since the whole problem boils down to understanding the asymptotic behavior of the numerical sequences PMST(n) and PTSp(n) defined by
(11.1) pmsT(n) = max min E lel: T is a spanning tree of V, and
V~ T ,T
(11.2) PTSP(n) max min E lel: T is a tour of V,,
V~ { T eeT
The following result from Steele and Snyder (1989) recalls the form of the probabilistic results for the TSP and MST, but repetition of form should not obscure the substantial shift in perspective and technique due to the absence of probability theory.
THEOREM 11. For any dimension d >, 2, there are constants OMST and OTSP satisfying 1 :~ PMST ' OTSP such that as n ,
(11.3) PMSM) i6MSTn (d l)ld and
Id l)ld
(11.4) PTSP(n) OTSpn
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 765
Exact asymptotic results for PMST and PTSp are recent, but considerable earlier work focused on bounds for PTSP and PMST which translate into bounds on k6MST and OTSP. For example, Verblunsky (1951) proved that in d = 2 one has PTsp(n) <, (2.8nW' + 3.15, and Fejes T6th (1940) established that PTSI,(n) and PN1ST(n) are both at least as large as (1 EX4/3) 1/4 n 1/2 for all n >, N(E). Next, Few (1955) improved the upper bound of VerbIunsky (1951) to PTSP(n) < (2n), /2 + 1.75 in d = 2 and obtained PTSI,(n) < d{2(d l#1 d)12d n (d 1)1d + 0(n' 21d) for general d >, 2. More recently, Moran (1984) obtained essential improvements on the upper bounds of Few (1955) for large values of d.
The simplest and sharpest bound on PTSP(n) in dimension two is given in Supowit, Reingold, and Plaisted (1983), where it is proved that the additive term 1.75 can be dropped from Few's upper bound to give PTS,(n) < (2n )1/2 . That paper also gives another new proof of the appealing lower bound due to Fejes T6th (1940) that PTSP(n) >, 2(12) 114 n 1/2 , and while the abstract of Supowit, Reingold, and Plaisted (1983) asserts pTsp(n) = a~n + o(~n ), that statement accidentally sacrifices precision for brevity. The text of Supowit, Reingold, and Plaisted (1983) is quite clear and no claim is made concerning results like Theorem 11.
The idea which underlies the exact asymptotic analysis of PMST(n) and pTsp(n) is that both sequences satisfy inequalities which bound their rates of growth and which express an approximate recursiveness. The following lemma looks technical, but it gets at the essence of the asymptoties PTSI,(n) and PMSTW.
LEMMA 2. If p(l) 0 and there is a constant c >, 0 such that
(11.5a) p(n + 1) < p(n) + cn 11d and
(11.5b) ii) Md ',o(k) md lk(d 1)1d r(k) ~< P(Md k),
where r(k) 0 as k then as n
(11.6) p(n) j3n1' 1)1d
for a constant )3.
To justify the hypotheses of Lemma 2 for pms.r and PTSP, one has to develop some basic properties of the MST and TSP. The following lemma points out one of particular interest because it provides a bound which does not depend upon 17.
LEMMA 3. There is a constant c such that for all x > 0, one has V MST(X) <, CX d' where VMST(X) denotes the maximum number of edges larger than x any minfinal spanning tree of {x , x,, . . . 1 XJ c [0, i]cl.
The worst case behavior of the MST and TSP has a parallel for minimal and greedy matchings. Steele and Snyder (1987) studied these problems in the context of general power weighted edges, and provided exact asymptotic results to complement the bounds obtained in Avis (1981, 1983).
The sequence associated with minimal matching is naturally
(11.7) P. (n) ~ max rnin E Jel': M is a matching of V,
V,, { M elm but for the honest analysis of greedy matchings it turns out to be necessary to
1
766 J. MICHAEL STEELE
consider the two sequences:
PG(n) = max max ~7, lel": M is a greedy matching of V, and
V,, { M ,M
(11.9) AG(n) = max min iel'. M is a greedy matching of V,,
m
V,, _ m
The reason one is forced to consider both PG and AG is that one can have matchings M, and M2 which are both bona fide greedy matchings of a set V {X, X21 ... , x,}, but for which
L~(M1) Jel` * L~(M2) le~a.
eeM, e (= M2
This phenomenon is due to the possibility of ties, but when investigating worst case configurations, ties cannot be shrugged off. In fact, they are surely to be expected in most optimal configurations. As it happens, one can establish a minimax result which says that AG(n) = PG(n) for all n >, 1, so after some worry, one comes back to the consideration of just two basic sequences. Moreover, the results for pm and PG are just as expected:
(11.10a) Pm(n) emn(' 6')1' and
(d a)ld
(11.10b) PG(n) = AG(n) OGn
where Pm and J6G are nonzero constants which depend on d >, 2.
The techniques behind (11.10a) and (11.10b) largely parallel the worst case analyses of the TSP and MST, but new turns are required, particularly for the greedy matchings. As in the stochastic analysis of the greedy matching, subadditive inequalities do not come easily from suboptimality, and one has to look hard at, the underlying algorithmic process.
12. Non Euclidean cousins. True to title and design, this review has focused on the. probabilistic and worst case analyses of classical problems of combinatorial optimization in Euclidean space, but some recent results on the probabilis.tic analysis of closely related non Euelidean problems are so interesting they require at least a brief look.
First, consider the weight M,, of the minimal spanning tree for the complete graph
on n vertices where the weight of any edge e = (i, j) is given by X,, and the
{Xij: 1 <, i < j < n} are independent random variables. Tirnofeev (1984) established a
number of interesting results concerning the behavior of M,, and in particular proved
(12.1) EMn < 3.29
provided the {Xj) are uniformly distributed in the unit interval [0, 11. Still, the crowning result in this direction is due to Frieze (1985):
(12.2) Mn ~(3)1F'(0)
where the convergence is in probability and in V, ~(3) = Wn In 3 = 1.202 and
F is the common distribution of the nonnegative independent random variables (Xij}.
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 767
The assignment problem with random costs has also had an interesting set of developments. If K,,, denotes the complete bipartite graph and independent uniform costs Xjj are associated with each edge of K,,,, then the assignment problem is to determine the minimum value A,, of a matching of K,,
The stochastic analysis of A, was considered in the Bachelor's thesis of Lazarus (1979) who showed FA, < c log n. Independently, Walkup (1979) established the remarkable fact in keeping with Tirnofeev's bound (12.1) that for all n >, 1 one has E4,, < 3. Most recently, Karp (1987) introduced a new conditioning method which was simpler than Walkup's method and which provided the sharper bound EA < 2. The development we wish to review in more detail on is the generalization and systematization of Karp's conditioning method provided by Dyer, Frieze, and McDiarmid (1986), and MeDiarmid (1986).
It is well known that the valu ' e A,, as well as all of the other functionals we have
reviewed can be expressed in terms of a linear programming problem. What is truly
remarkable is that one can obtain good bounds on EA, and similar quantities within
that general framework.
Dyer, Frieze, and MeDiarmid (1986) consider the general problem:
n
(12.3) minimize E cixi
j 1 40
n
subject to E aijxj ~ bi, i ~ 1, 2, , m,
j 1
xj >, 0, j = 1, 2, n.
The coefficients c, of the objective function are assumed to be independent, nonnegative random variables (with possibly different distributions), but all of the remaining parameters are assumed to be known constants. The Dyer Frieze McDiarmid inequalities relate the pointwise (random) optimal solution z* of (12.3) to the fixed feasible solutions of (12.3). For example, if the cj are independent and uniform on [0, 11 and Ifh 1~2.... ~ 'f,, is a fixed feasible solution of (12.3), then the simplest of the Dyer Frieze McDiarmid inequalities is
(12.4) Ez* < m max{,~i: j 2,..., n}
To see how (12.4) relates to Karp's bound on MA,) we note the assignment problem can be written as
(12.5) minimize z ci,ixii
j,~ n
subject to xi,i = 1, 1 i
1 < j 17
xij = 1, 1 j n, and
xii > 01 j < n.
Looking at the assignment problem in terms of the formulation (12.3), we see that
768 J. MICHAEL STEELE
m = 2n and also that ~,j ~ 1In is a feasible solution. Consequently, inequality (12.4) implies Karp's inequality MA,) < 2.
The main result of Dyer, Frieze, McDiarmid (1986) is an apt generalization of inequality (12.4) to a class of random cost variables which retain a conditioning property of the uniform. Specifically, the generalization concerns independent random variables c, for which there is a 0, 0 < 8 < 1 such that
(12.6) E(cjIci ~> h) > E(cj) + 8h
for all h >. Owith P(cj >, h) > 0.
The main inequality of Dyer, Frieze, and MeDiarmid (1986) can be written as
(12.7) E(z*) < 8 ' max { ~', ~jEci~
S: ISJ=171 iES
To see how (12.7) contains the handy inequality (12.4), we first note that for uniformly distributed cj we can take 0 = 1/2 in (12.6) and Ec, = 1/2, so the right side of (12.4) certainly majorizes the right side of (12.4).
The great distinction between the non Euclidean cousins considered in this section and the problems considered previously rests entirely in the assumption of independence in the costs (cj}. It is still hard to see how the methods of Dyer, Frieze, and McDiarmid (1986) can be used where the dependence of the costs carries as much complexity as it must in Euclidean problems, but nevertheless it seems likely that the Dyer Frieze McDiarmid inequalities will become part of the standard machinery of probability as it is applied in combinatorial optimization.
13. Conclusion. One intention of this review has been to show that the work initiated by Beardwood, Halton, and Hammersley (1959) and fueled by Karp (1976) has good prospects of growing into a rich and useful theory. The review should have also conveyed the spirit of a young theory with open problems, rough edges, and many opportunities for invention.
Added in Proof. The conjecture of R. Bland discussed in h has been proved recently by D. Aldous and the author by techniques unrelated to those of this survey
Acknowledgement. A preliminary version of this review supplemented three lectures given at Cornell University as part of the Year in Discrete Optimization organized by the Center of Applied Mathematics and the Department of Operations Research and Industrial Engineering. The exposition has profited from the comments of Robert Bland and Timothy Snyder.
References
Adler, R. (1986). Comments in Collected Works of S. Kakutani, Vol. 11, R. R. Kallman (Ed.), Birkhauser, Boston, 444.
Ajtai, M., Korn16s, J. and Tusnfidy, G. (1984). On Optimal Matchings. Combinatorica 4 259 264.
Avis, D. (1981). Worst Case Bounds for the Euclidean Matching Problem. Comput. Math. Appl. 7 251 257.
(1983). A Survey of Heuristics for the Weighted Matching Problem. Networks 13 475 493.
Davis, B. and Steele, J. M. (1988). Probabilistic Analysis of a Greedy Heuristic for Euclidean Matching. To appear in Probability in the Engineering and Information Sciences.
Bartholdi, J. J. and Platzman, L. K. (1988). Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space. Management Sci. 34 291 305.
COMBINATORIAL OPTIMIZATION IN EUCLIDEAN SPACE 769
Beardwood, 1, Halton, J.H. and Hammersley, J. M. (1959). The Shortest Path Through Many Points. Proc. Cambridge Philos. Soc. 55 299 327.
Bingham, N. H. (1981). Tauberian Theorems and the Central Limit Theorem. Ann. Probab. 9 221 231.
Coffrnan, E. G. and Shor, P. W. (1989). A Simple Proof of the 0(~n log3/4n) Up Right Matching Bound, Technical Report, AT & T Bell Laboratories.
Dyer, M. E., Frieze, A. M. and McDiarmid, C. J. H. (1986). On Linear Programs with Random Costs. Math. Programming 35 3 16.
Efron, B. and Stein, C. (1981). The Jackknife Estimate of Variance. Ann. Statist. 9 586 596.
Fejes T6th, L. T. (1940). Uber einen geornetrische Satz. Math. Z. 46 83 85.
Few, L. (1955). The Shortest Path and the Shortest Road through n Points in a Region. Mathematika 2 141 144.
Fisher, M. L. and Hochbaum, D. S. (1980). Probabilistic analysis of the Planar K Median Problem. Math. Oper. Res. 5 27 34.
Frieze, A. M. (1985). On the Value of a Random Spanning Tree Problem. Discrete Appl. Math. 10 47 56.
Ghosh, H. W. (1949). Expected Travel among Random Points. Bull. Calcutta Statist. Assoc. 2 83~87.
Gilbert, E. N. and Pollak, H. 0. (1968). Steiner random minimal trees. SIAM J. Appl. Math. 16 1 29.
Halton, J. H. and Terada, R. (1982). A Fast Algorithm for the Euclidean Traveling Salesman Problem, Optimal with Probability One. SL4MJ, Comput. 1128 46.
Hartmann, M. (1987). Tauberian like Theorems for Upper and Lower Bounds. Report No. 87471 OR, Institut filr Okonometrie und Operationes Research, UniversitSt Bonn.
Hochbaum, D. and Steele, J. M. (1982). Steinhaus' Geometric Location Problem for Random Samples in the Plane. Adt). in Appl. Probab. 14 55 67.
Jessen, R. J. (1942). Statistical Investigation of a Sample Survey for Obtaining Farm Facts. Bull. Iowa State Coll. Agricultural Res. 309.
Karlin, S. and Rinott, Y. (1982). Application of ANOVA Type Decompositions for Comparison of Variance Statistics Including Jackknife Estimates. Ann. Statist. 10 485 501.
Karloff, H. (1989). "How Long Can a Euclidean Traveling Salesman Tour Be? SIAM J. Discrete Math. 2 91 99.
Karp, R. M. (1976). The Probabilistic Analysis of Some Combinatorial Search Algorithms. Algorithms and Complexity: New Directions and Recent Results J. F. Traub (Ed.), Academic Press, New York, 1 19.
(1977). Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plane. Math. Oper. Res. 2 209 224.
(1979). A Patching Algorithm for the Non symmetric Traveling Salesman Problem. SIAM J. Comput. 8 561 573.
(1987). An Upper Bound on the Expected Cost of an Optimal Assignment. 1 4, in Discrete Algorithms and Complexity: Proc. Japan US Joint Seminar D. Johnson, et al. (Eds.), Academic Press, New York.
Lenstra, J. K., McDjarmid, C. J. H,, and Rinnooy Kan, A. H. G. (1984). Probabilistic Analysis of Combinatorial Algorithms: An Annotated Bibliography in Combinatorial Optimization: Annotated Bibliographies M. 0'hEigeartaigh, J. K. Lenstra and A. H. G. Rinnooy Kan (Eds.), John Wiley and Sons, New York.
and Steele, J. M. (1985). Probabilistic Analysis of Heuristics. The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization Lawler, E. L., et al. (Eds.), John Wiley and Sons, New York, 181 206.
Kern, W. (1986). On the Rate of Convergence of Some Stochastic Processes. Technical Report No. 85.26, Mathernatisches Institut, Universit5t zu K61n, West Germany.
Kesten, 11. (1973). Contribution to J. F. C. Kingman. Subadditive ergodic theory. Ann. Proball. 1 883 909.
Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. B. G. and Shmoys, D. B. (1985). The Traveling Sidesinan ProbIcm: A Guided Tour of Combinatorial Optimization. John Wiley and Sons, New York.
Lazarus, A. (1979). The Assignment Problem with Uniform (0, 1) Cost Matrix. Unpublished B,A. Thesis, Department of Mathematics, Prinecton University, Princeton, NJ.
Leighton, T. and Shor, P. (1986). Tight Bounds for Minimax Grid Matching with Applications to the Average Case Analysis of Algorithms. Proc. 78th ACM Syinj). Theory of Computing, 91 103.
Mahalanobis, P. C. (1940). A Sample Survey of the Acreage under Jute in Bengal. S(I771o,i 4 511 531.
Marks, E. S. (1948). A Lower Bound for the Expected Travel among m Random Points. Ann. Math. Statist. 19 419 422.
MeDiarmid, C. (1986). On the Greedy Algorithm with Random Costs. Math. Programming 36 245 255.
Milne, S. C. (1980). Peano Curves and Smoothness of Functions. Adu. in Malh. 35 129 157.
Moran, S. 0984)~ On the Length of Optimal TSP Circuits in Sets of Bounded diameter. J. Combinatorial
Theory Ser. B 37 113 141.
Papadirnitriou, C. H. (1977). The Euclidean Travelling Salesman Problem is NP Completc. Theoretical Computer Sci. 4 237 244.
1
J. MICHAEL STEELE
Papadimitriou, C. H. (1978). The Probabilistic Analysis of Matching Heuristics. Proc. 15th Annual Conf.
Comm. Contr. Computing, Univ. Illinois, Champaign Urbana.
(1981). Worst Case and Probabilistic Analysis of a Geometric Location Problem. SIAM J. Comput.
10, 3 542 557.
R~dei, L. (1934). Ein kornbinatorischer Satz. Acta Szegetl 7 39 43.
Rhee, W. T. (1988). On the Variance of the Stochastic Traveling Salesperson Problem. Technical Report,
Ohio State University.
and Talagrand, M. (1986). Martingale Inequalities and the Jackknife Estimate of Variance. Statist.
Probab. Lett. 4 5 6.
and (1987). Martingale Inequalities and NP Complete Problems. Math. Oper. Rcs. 12
177 181.
and (1989a). Martingale Inequalities, Interpolation, and NP Complete Problems. To
appear in Math. of Oper. Res.
and (1989b). A Sharp Deviation for the Stochastic Traveling Salesman Problem. Ann.
Probab. 17 1 8.
Richardon, D. (1973). Random Growth in a Tessellation. Proc. Cambridge Philos. Soc. 74 515 528.
Rootz6n, H. (1983). Central Limit Theory for Martingales via Random Change of Time. Probab. Math.
Statist. Essays in Llonot. of Carl Gustat, Esseen. A. Gut and L. Hoist (Eds.), Department of Mathematics, Uppsala University, Uppsala, Sweden.
Rosenkrantz, D. J., Stearns, E. and Lewis, P. M. (1977). An Analysis of Several Heuristics for the Traveling
Salesman Problem. SL4M J. Comput. 6, 3 563 58 1.
Shamir, E. (1989). Presentation at Bell Communications Research, Morristown, NJ, February.
Shor, P. W. (1985). Random Planar Matching and Bin Packing. Ph.D. Thesis, Massachusetts Institute of
Technology, Cambridge, MA.
Steele, J. M. (1981a). Subadditive Euclidean Functionals and Non linear Growth in Geometric Probability.
Ann. Probab. 9 365 376.
(1981b). Complete Convergence of Short Paths and Karp's Algorithm for the TSP, Math. Oper.
Res. 6 374 378.
(1982). Optimal Triangulation of Random Samples in the Plane. Ann. Probab. 10 548 553.
(1986a). Probabilistic Algorithm for the Directed Traveling Salesman Problem. Math. Oper. Res. 11
343 350.
(1986b). An Efron Stein Inequality for Non symmetric Statistics. Ann. Statist. 14 753 758.
(1988). Growth Rates of Euclidean Minimal Spanning Trees with Power Weighted Edges. Ann.
Probab. 16 1767~1787.
Shepp, L. A. and Eddy, W. F. (1987). On the Number of Leaves of a Euclidean Minimal Spanning
Tree. J. Appl. Probab. 24 809 826.
and Snyder, T. L. (1987). Worst Case Growth Rates for Minimal and Greedy Matchings with
Power Weighted Edges. Technical Report, Princeton University, Program in Operations Research and Statistics.
and (1989). Worst Case Growth Rates of Some Classical, Problems of Computational
Geometry, SL4MJ. Computation 18 278 287.
Supowit, K. J., Reingold, E. M. and Plaisted, D. A. (1983). The Traveling Salesman Problem and Minimum
Matching in the Unit Square. SL4M J. Comput. 12 144 156.
Talagrand,'M. (1989). Complete Convergence of the directed TSP preliminary manuscript.
Timofeev, E. A. (1984). Random Minimal Trees. Theory Probab. Appl. 29 134 141.
Troyon, M. (1988). Quelques Heuristiques et Resultats Asymptotiques pour Trois Problems d'Optimisation
Combinatoire. Ph.D. Thesis, Ecole Polytechnique Federale de Lausanne, Laussane, Switzerland.
Verblunsky, S. (1951). On the Shortest Path through a Number of Points. Proc. Amer. Math. Soc. 2
904 913.
Vitale, R. A. (1984). An Expansion for Symmetric Statistics and the Efron Stein Inequality. Inequalities in
Statistics and Probability IMS Lecture Notes Monograph Series Vol. 5, Y. L. Tong (Ed.), 112 114. Walkup, D. W. (1979). On the Expected Value of a Random Assignment Problem, SIAM J. Comput. 8, 3
440 442.
Weide, B. W. (1978). Statistical Methods in Algorithm Design and Analysis. Unpublished Ph.D. Thesis,
Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA.
DEPARTMENT OF STATISTICS, WHARTON SCHOOL, UNIVERSITY OF PENNSYLVANIA,
PHILADELPHIA, PENNSYLVANIA 19104