Mathematical Programming 53 (1992) 127146 127

NorthHolland

Euclidean semimatchings of random samples

J. Michael Steele

Department of Statistics, VVharton School, University of Pennsylvania, Philadelphia, PA 19104, USA

Received 19 August 1988

Revised manuscript received 8 February 1990

A linear programming relaxation of the minimal matching problem is studied for graphs with edge weights determined by the distances between points in a Euclidean space. The relaxed problem has a simple geometric interpretation that suggests the name minimal semimatching. The main result is the determination of the asymptotic behavior of the length of the minimal sernimatching. It is analogous to the theorem ofBeardwood, Halton and Hammersley (1959) on the asymptotic behavior of the traveling salesman problem. Associated results on the length of nonrandom Euclidean semimatchings and large deviation inequalities for random semimatchings are also given.

AMS 1980 Subject Classifications: Primary 05C05; Secondary 60F15.

Key words: Minimal matchings, subadditive processes, complete convergence, large deviations, asymptotic methods, relaxation methods.

1. Introduction

Let G=( V, E) be a graph such that for each edge e c= E there is an associated weight w,. We are concerned here with the solutions to the following linear program:

z = min 1 x,w, (1.1a)

X eeE

subject to 1 x, = 1 for all v E: V, (1.1b)

c meets v

x, 0 for all e e E. (1.1c)

If G is the complete bipartite graph*K,,, then (1.1) becomes an assignment problem, and the wellknown Integrality Theorem tells us that (1.1) has a solution such that each x, is an integer, specifically xe = 0 or 1 for all e (see, e.g., Chvdtal, 1983, p. 327; or Lovdsz and Plummer, 1986, p. 269).

A less wellknown result of Balinski (1965) tells us that if G is the complete graph K,, then there is a solution of (1. 1) in semiintegers, i.e., Xe = 0, 12, or 1 for each e e E. For this reason (and additional reasons to be reviewed shortly), the linear

Research supported in part by NSF Grant #13MS8812868, ARO contract DAAL0389G0092.POOI, AFOSR8908301.A and NSAMDA904892034.

128 J. M. Steele / Randoin sernimatchings

program (1.1) will be called the semimatching problem. A proof of Balinski's theorem is given in Lovdsz and Plummer (1986, p. 291), and the result is more subtle than one might guess. It is established with help from the classic result of Petersen on the decomposition of regular graphs into 2factors. One can also find a discussion of the semiinteger nature of the solutions of (1.1), and an indication of proof of Balinski's theorem in Yemelichev et al. (1984, p. 175).

The intention of this paper is to investigate the behavior of the solutions to (1.1) where the vertices of G are points V,, V2 V, in Rd and where the weight w, associated with edge e = (vi, vi) is the Euclidean distance 1 Vi ~jj. For the main results, we further assume that the points vi, 1 i n, are determined by a probability model. In particular, we treat the case where the points are modeled as independent identically distributed random vectors in Rd. In that situation, we are especially concerned with the growth rate of the value of the objective function as n becomes large.

Two branches of optimization theory motivate this investigation. First, the semimatching problem illustrates the interplay between linear programming and combinatorial optimization. The classic paper of Edmonds (1965a) provided one of the earliest applications of linear programming to combinatorial optimization by showing that (1.1) can be supplemented with additional linear constraints to obtain an LP formulation for the general problem of minimal matching in a weighted graph. It turns out that an exponential number of additional constraints are required, but by appropriate sequential generation of the constraints, an optimal solution can be determined in polynomial time. Intriguingly, Edmonds (1965a) was among the first works to draw attention to the fundamental distinction between polynomial time and exponential time algorithms (see also Edmonds, 1965b, 1970).

The second line of development motivating the investigation of semimatchings hinges on a geometrical interpretation. Since the value of x,, here called the loading factor of e, can only be 0, 12, or 1 in a minimal solution to (1.1), one can easily show that any minimal solution consists of a union of isolated edges with loading 1 and a collection of odd cycles that has all edge loading equal to 12. This interpretation of the LP (1.1) shows that the solutions of (1.1) are close to the usual notion of minimal matching. Still, there are some significant theoretical differences between semimatching and ordinary matchings. One modest difference that nevertheless makes semimatchings theoretically more attractive than minimum weight perfect matching is that there is no need to distinguish between odd and even values of n.

The geometric interpretation of semimatchings also connects them with the theory of subadditive Euclidean functionals. That theory begins with work on the asymptotic behavior of the traveling salesman problem by Beardwood et al. (1959), and its importance for combinatorial optimization is made clear in the work of Karp (1977) that provides a polynomial time probabilistic algorithm for the TSP.

The main result of this paper is the following asymptotic result for Sn that is analogous to the result obtained for the traveling salesman problem by Beardwood et al. (1959).

i

fM. Steele / Random seinimatchings 129

Theorem 1. Suppose that Vi, 1 i < oo, are independent random variables with the uniform distribution on [0, 1]d , and let S,, = S(V., V2, ., Mdenote the cost of a minimal semimatching of {V, V,..., Vj. For any d 2, there is a constant Cd > 0 such that

liM SnIn (dl)ld = Cd (1.2)

with probability one.

For d = 2 the analogue of Theorem 1 for minimal matchings was first given in Papadimitriou (1977). After developing some basic geometry of semimatchings, an abstract version of Theorem 1 will be stated in Section 3, and at that point we will consider how the framework of Papadimitriou (1977) differs from the present approach.

The minimal semimatching functional S is also wellbehaved enough to permit the ext~nsion of Theorem 1 to more general distributions. In the following result, the constant Cd is the same as that given in the limit (1.2).

Theorem 2. If Vi, 1 i < oo, are independent random variables with distribution g with compact support and absolutely continuouspart dii,, =f(x) dx then withprobability one,

liM S( V1, V2, M/ n (dl)ld = C, fR f(X)(d111d dx. (1.3)

nw d

The approximation process by which one goes from the asymptotic theory of the uniform distribution to the general distributions of Theorem 2 is technical, and since the required approximation techniques are remote from the potential applications of the result, the proof of Theorem 2 will only be sketched.

Given the current state of development of the theory of subadditive Euclidean functionals, Theorems 1 and 2 rest substantially on nonprobabilistic insights, and thus much of the work of this paper is nonprobabilistic. In particular, the next section provides three geometric inequalities that serve to articulate the structural parallels between semimatching and the traveling salesman problem (TSP). In fact, once one makes explicit this underlying structural communality, the techniques of the proof of Theorem 1 are seen to be as pertinent to the theory of the TSP as to the theory of semimatchings. In this respect it is worth noting that the proof given here contains several twists that contribute to the general theory of subadditive Euelidean functionals. These features of the proof are pointed out as the details are given.

2. Geometry of semimatchings

The two geometric properties that contribute the most to the asymptotic analysis of the minimal Euclidean semimatching are the following: (1) the subadditivity

130 1M. Steele / Random semimatchings

expressed in Lemma 1, and (2) the smoothness property expressed in Lemma 2 that says as vertices are added or deleted the cost of a minimal semimatching changes only modestly.

We let QO = [0, 1]" denote the unit cube in Rd , and we divide this cube into md

congruent subcubes Qi, 1 i Md. If V1, V2 V, is a fixed set of points in Q,

we write S(Q) for the cost of the minimal semimatching of the points in

{V,, V2, . . , v,} n Q. The first lemma follows from the observation that the union

over 1 __ i __ M d of any feasible semimatchings of Qi n {v,, v,,. . . , v,} provides a

feasible semimatching of QO n {v,, V2, .. 1 V0.

Lemma 1. For any n points {V,, V2, Vn} and any integer m, we have

'd

S(Q0) 1 S(Q). E] (2.1)

i=1

The simplicity of this inequality should not hide its power. One can extract considerable asymptotic information from (2.1) when it is combined with homogeneity and translation invariance.

To make use of probabilistic information on the distribution of random points it is also important to know how S changes as points are added or deleted. The next lemma provides this information and thus provides the required surrogate for the monotonicity that one has for subadditive functionals like the TSP.

Lemma 2. For any n 2, we have

IS(V1, V2,. .., V.) S(V1, V2, Vn+1)l 1 d2(Vn+ 1; V1, V2, 5 Vn) (2.2)

where

dAV; Y1, Y2, ..., Yn)

= min{r: 1 v yi 1 r and 1 v yjI rfor some 1 i

Proof. We first show S(V1, V2, .., V.+1) cannot be much bigger than S(V1, V2~ ... 9 Vn). A key role in the proof is played by the nearest neighbors of v,+,, and z will denote any such neighbor.

In a minimum weight semimatching of {v,, V2,..., VJ, vertex z can occur on an edge e = (z, z) with loading 1, or z can occur on an odd cycle with neighbors z' and z" such that each of the edges (z, z) and (z, z") each have loading 12. If (Z, Z)

has loading 1 we build feasible loading of {VI, V2, Vn+l} by the following

assignments:

el = (z, v,+,), x., =

2 5

i

e2 = (Z', V.+ 1), Xe2 = 2,

i

e3 = (z, Z), Xe3 = 2.

i

i i

i

1~

J.M. Steele / Random semimatchings

131

This new loading spans {v,, V2, . * . , Vn+l}, and it exceeds the cost of the minimal loading Of {VI, V2, .. . 1 Vn} by, at most,

Al = 5,1v,+~ Z1 +'iv~

2

~'1Vn+1 Z1 +21flVn+. ZI +I Z Z'I} 2'1Z Z'I =I V~+~ ZI.

(2.3)

In the case that z occurs on a triangle (z, z), (z, z"), (z', z") we change the minimal

loading of {v,, v VA by setting

e, (z, v,,), X,

e2 (z', z"), X '2

e3 (z, Z), xe3 0,

e4 (,, z"),

This new loading increases the cost of the minimal loading of {v Vn} by, at most,

1 lz Z'] 'iz Z"1 1 v, Z1. (2.4)

1A2 = 1 V~ll Z1 + 31Z'_ Z"I 2 2

The third case to consider is that z occurs on an odd cycle containing at least five vertices. If z' and z" are the neighbors of z on this cycle we change the loading to the following:

el = (z, v.+,), x, = 1,

e2 = (z, z), X 12 = 0,

e3 = (Z, Z"), X~3 = 01

e4 = W, z"), X.~ = 2.

This again provides feasible loading and, even though the presence of an even cycle marks it as suboptimal, we can check that it is good enough by the following bound on the incremental cost:

1A3 = 1 V.,. Z1 121 Z Z'I 211 Z Z1 + 121 Z' Z1 1 V~ Z1.

Summarizing (2.3), (2.4) and (2.5) we have

S(V1 , V2, V~+ 1) S(V1 , V2, V.) + min 1 Vi Vn+ 1 1,

1 Siln

(2.5)

(2.6)

which is a bit sharper than we need to prove the first half of inequality (2.2).

We now need to obtain an upper bound on S(V1, V2,. ..,V.) in terms of S(V1, V2~ .... 3 Vn+l). The simplest case occurs when v,+, is on an odd cycle in a minimal semimatching Of {VI, V2, . . ., V~+1}. If the neighbors of v,+, are z and z' and the cycle is a triangle, we just give (z, z) a loading factor of one to get our feasible matching of {v,, V1, . . . , Vn}. Furthermore, if v,,, is on a cycle of cardinality five or greater, we just give (z, z) a loading of 21. In either of these cases, we see there is a feasible semimatching for {VI, V2, V,} that has cost bounded by S(V1 , V2, . . . , Vn+l).

i

1

132 JM. Meele / Random semimatchings

We now confront the trickiest case. Suppose Vn11 is on an edge (v,,, z) with loading factor equal to 1. We let w be a vertex other than z that is within a distance d, of v,,,,. By the definition of d2, at least one such w must exist.

We can either have w as a vertex in an odd cycle or as a vertex on an isolated edge. If w is on a single edge (w, w') with loading 1, we consider the new loading factors given as follows:

1

e 1 (z, W), W,, 2,

e2 (W, W), W,, 2',

e3 (Z, W1 WI'3 2.

From this loading allocation, we have

S(V1, v,, VJ S(V', V2,.V.+i) 1 v., Z1 +2,1z W1

+ 1

21Z W1 11 W W11 (2.7)

and since

lzwl+lzw'i21zwl+lww'l and lzwl1v,+,zl+lv,+,wl, we have

S(V1, V2, Vj S(V1, V2, Vn+l) 1Vn+l Z1 +1z W1

S(V, V2,.. Vn+l) +IV.+i W1. (2.8)

Next we consider the case that w is on an odd cycle with neighbors (w', W). If the cycle is a triangle we take new loadings

e, = (z, W), We, = l,

e2 = (W', W'), WC2 = 1,

and if the cycle is of size five or greater we take the loadings

e, = (z, W), We, = t

e2, = (W W We2 = 1

2.

In either of these two situations we find that S(vi, V2, Vn+l) S(V1, V2 5 Vn)

is bounded by

2 2 W

1Vn11 Z1 +~Z W1 11W W1 121W W1 + 11W'

By the triangle inequality, the sum of the last three terms is bounded by 0 and z w is bounded by IZ Vn1A + IV,,+~ wl. Thus, we find the bound,

A, 1 v,+, wl d2(V~+1; V1, V2, . , Vn). (2.9)

i

i

J. M. Steele / Random semimatchings 133

From inequalities (2.1), (2.4), (2.8) and (2.9), the proof of Lemma 2 is complete. n

Lemma 3. For any n 2, we have

1,2 (dl)ld

S(V', V, Vn) 8d n (2.10)

Proof. If Md < n12 (M + 1) d' then one of the cubes Qi of the decomposition of [0, fl" into Md cells of side m' must contain at least three points. Since m 'd 1/2 is the diameter of Qi we see that there is thus a 1j_

m 2(m+l) 2(n/2) we have

S(V, V25. .V,i)

~ S(V1, V2, .. ., vj,, vj+l, . . . , v.) +21 +11d d 1/2 n_11d. (2.11)

Applying the same argument to the n 1 set {v,, V2,. ~j1, Vj+1, V0 and

continuing successively, we find

S(V1, V2, Vn)

n

21+ 11d d 1/2 1 j11d ~2 (d+l)ld d 3/2 (d 1)1n (dl)ld. (2.12)

n=l

Since 2 1d+1)1d dl(d 1)_8 ford 2, (2.12) is stronger than the required bound. E

3. Underlying structure

As we have already noted, a close connection exists between the probability theory of semimatchings and the traveling salesman problem. This connection can be made most explicit by laying out some of the abstract properties of the semimatching functional that connect semimatchings with the TSP and other subadditive Euclidean functionals. Very few properties of S are needed to show that the conclusion of Theorem 1 is valid. Explicitly, Theorem 1 will be proved by appeal to only the following:

d

(AI) S(ax,, aX2,..., ax,) = aS(Xl, X2,..., X.) for all a > 0 and Xi E R

d

(A2) S(XI+YI,X2+Y,...,X.+Y)=S(X15X2.... 1 Xj for all y and xi in R

(A3) IS(X., X2.... 5 Xn, Xn+l) S(Xl, X2,. .. 1 X1)l I dAXn+l; Xl, X2, XJ for all

d n 3 and xi in R .

11d)

_l_d

(A4) S({Xl, X2, Xn} n [0, i= 1 S({Xl, X2,... 5 X0 n Q).

If one could replace (A3) by the stronger monotonicity condition

S(Xl, X2, . . . , Xn+l) S(Xl, X2,. . . , X.), then by results of Steele (1981a) conditions

i

i

i

134 J.M. Steele / Random semimatchings

(AI) through (A4) would be enough to guarantee Theorem 1. Since one can easily provide examples that show S is not monotone, we are compelled to study semimatchings through surrogate inequalities like (A3). In contrast to its deficient monotonicity, semimatchings have rather stronger subadditive properties than one typically finds. In the general theory of subadditive Euclidean functionals, one relaxes (A4) to

S({Xl, X2 X.} n [0, t]d)

.d

Y_ S({XI, X2, Xj n tQi) + CtMd1, (3.1)

i=1

and this relaxation is surely worthwhile since without it the theory would not include the TSP.

We should also note that in Papadimitriou's formulation of the limit theory for the minimal matching M(x, x,,... 1 XJ Of{Xl, X2 .... 1 Xj _ R2 , a key role is played by a lower bound that complements (A4) or (3.1). Specifically, the proof sketched in Papadimitriou (1977, p. 369) called upon the following property of minimal matchings in R 2:

M({Xl, X2, X, } n [0, 1]2)

,2

Y {M({XI,X2, ,Xn}nQi)2laQil}. (3.2)

i=1

Here laQil denotes the length of the boundary of the square Q. One of the issues that arises when one considers matchings or semimatchings in R d , d > 2, is the determination of a suitable replacement for the laQil terms. Because of this difficulty, an approach based on (AI)(A4) lead to a more straightforward theory that is still well suited for applications. The main drawback of the axiomatization (A1)(A4) is that one can no longer appeal directly to the proof of Beardwood et al. (1959), although, because of the considerable complexity of that proof, perhaps this drawback is really a blessing.

The bottom line is that most of the difficulties that arise in the limit theory for semimatchings come from its failure to be monotone. Moreover, the general theory of subadditive Euclidean functionals benefits by seeing how this difficulty can be overcome.

4. Analysis of the expected value

The proof of Theorem 1 is perhaps most easily explained by dealing separately with the asymptotic behavior of ES, and the behavior of S. ES.. The first step in the analysis of ES,, is the introduction of a Poissonization device that permits the expeditious use of (Al), (A2) and (A4). The second step is to extract the asymptotics of ES, from the asymptotics of the Poissonized sequence. In this step our analysis

i

i

J.M. Steele / Randoin semimatchings 135

leans heavily on (A3) and the fact that the Poisson distribution concentrates almost all of its mass in an interval [A A', A + A'Y ] if y > 2'

If we let N be a Poisson random variable with mean A, and we choose N points in [0, 1]d independently according to the uniform distribution, then each of the Md subcubes Qi contains Ni points, where the Ni are independent Poisson random variables with mean A/ Md. If.we now set

O(A) = ES(X,, X2,. . ., XN) (4.1)

where the Xi are independent and uniformly distributed, then from (2.1) we see that

0 (A) Mdl

After substituting A ~d for A and dividing by Md 'A' with a= (d I)/ d, we have

O(Md,k)/(Md A)'O(A)/A', m1. (4.2)

Now, given any E > 0 and k > 0 we can choose an interval (a, b) (a (E, k), b (E, k)) such that for all A c (a, b) we have

(p (A)/ A E + inf (p (u)l u'. (4.3)

k

Applying (4.2) to (4.3), we find

O(Md A)/ (mA)' E + inf 0 (u)l u' (4.4)

u k

for all m and A E (a, b), hence

0 (x)l x' c + inf 0 (u)l u' (4.5)

A~k

for all X E: (Md a, Md b)=U. For ma' 1d 1(b 11d a 11d) the intervals

(Md Md +1)d (M+I)d d

a, b) and ((m a, b) overlap, so U contains (mo a, oo) where %

is the least integer as great as a' 1d / (b'ld a 11d). We can thus conclude from (4.5)

that

litn sup O(A)/A' lim infO(A)/A' + e. (4.6)

A~ A0

Since (4.6) holds for all E > 0, the limit of O(A)/A' exists as A 00.

Now, if we let

s. = ES. = ES(Xl, X2,. . ., XJ, (4.7)

the asymptotics we have established for (fi(A) can be used to obtain the asymptotics of s,. If we expand 15(A) by conditioning on N, we find

'0

(P(A) E(S(Xl,X2,...,X.))P(N=n)=e' s.A"1n!, (4.8)

n=0

so we have

(P(A)=eA 1 s,A"In!cA'. (4.9)

n=0

i

i

136 J.M. Steele /Random sernimatchings

The extraction of the asymptoties of sn from that of O(A) can be achieved by appeal to classical Tauberian theorems, or by completely elementary means. We will pursue the latter route, but first we need to verify that sn is reasonably smooth. We use 11 Y11, = (E Y')'11 to denote the L' norm of E

Lemma 4. There is a constant a, depending only on d such that for independent, uniformly distributed random variables X,, the variables Yn= d,(Xn, ; Xl, X2, .. . , Xn) satisfy

11 Yn 11, ,,,(pln)~l" (4.10)

for all n 1. Consequently, we also have r 'n h n,

fo 2 2

lsn Sn+d < ad211eln 1/d lhi. (4.11)

Proof. We first bound P(Y,, y) by conditioning on Xn, ~ and applying geometric considerations. For any 0 < y < 1 and for all X E [0, 1]d = Q, we have the elementary geometric bound

P(IXi xl y) 1 2 dOdyd' (4.12)

where Wd is the volume of the unit sphere in R d . To see why the factor 2 d is needed, just note that (4.12) becomes an equality if x is one of the corners of the cube.

Since {Yn y} if and only if at most one of the events Ai = fiXi xl

Yn Y) (1 d2 dyd)n + nWdyd (1 2d(Odyd)1 (bn(y), (4.13)

and, for 1 Y d 1/2 we have P(Y, y) bounded by On (1). Naturally, ^ Y, y) = 0

1/2

if y d

If we multiply these bounds by pyP', apply the bound (1 x) e', and integrate using 1 y` e Oyd dy = d 'fl "ldr(a 1d) we can complete the proof of (4.10) by

0

applying the bound I'(x) x'.

To prove (4.11), we only have to note by (4. 10) and the restrictions on h that

S~ Sn+h ad 1 2 11d k 11d '< ad 2 11d n 11d lhi. [1

nihik

The preliminaries are out of the way, and we can now establish the main result of this section.

Lemma 5. There is a constant Cd > 0, such that as n 00,

(dl)ld

s, cdn (4.14)

J. M. Steele / Random senflmatchings 137

Proof. We first recall a classical bound on the tail of the Poisson distribution (see, if 1< _Y<2

e.g., Hardy, 1949, p. 170); 2 3 then, as A 00,

e'A/ k! = 0(exp(A (4.15)

for any 77 < 2y 1. We also note that (4.15) further implies that for each fixed 6 > 0,

1 k' e lAk IC = 0(exp(A '/2)). (4.16)

k:1 A\ ~>,\ 1

For easy checking, we will apply (4.15) and (4.16) with y and q We let A

5 6

be any positive integer and use (4.11) together with the crude bound sI, d 1/2 k to estimate s,, in terms of O(A) as follows:

(MA) = SA + Y (sl, s,) e IA k IC

k=0

= S, + 0 (A + k) e"A k 1M

( k: lkA 1 ' A3/5

+0 Y" A 3/5 A"d e"A k 1M

GlkA I

= S, + 0(exp(A 1/6 /2)) + O(A

Since P(A)= CA Id 1)1d + o(A Id111d ) by (4.9), we thus have s, = cA (dOld + o(A Id ')/') as well. The fact that cd > 0 follows from the fact that by elementary geometric probability such as applied in (4.12) one has a c> 0 such that E minj

One finds a familiar pattern in the derivation of the asymptotics of 0 (A) by means of the subadditivity argument given in equations (4.2) through (4.7). On the other hand, the use of Hardy's bound on the Poisson tails has not been used before in the context of subadditive Euclidean functionals, and the introduction of this bound provides a simpler and more powerful approach than the Tauberian arguments used in K.arp and Steele (1985) or Steele et al. (1987). From the perspective of the general theory, where,there is some benefit to working only with onesided bounds, the Tauberian arguments retain some benefits; but, where one has twosided control of s. s,,h as given by Lemma 4, the line of argument given by (4.15)(4.17) seems to be preferable.

5. Finishing the proof of Theorem 1

(dl)ld

Now that we know ES, cdn ' the asymptotic behavior of the random variable S, is essentially reduced to obtaining good bounds on the central moments E (& _ Sjk, or the tail probabilities ^ & s, 1 t).

i

1

i

1

138 J.M. Steele / Randoin semimatchings

By modifying the methods used for the TSP in Steele (1981b), one can show by means of the inequality of Efron and Stein (1981) that E(S,, Sn )2= Var Sn is Of order 0(n 121d). With such a bound on Var(Sn), one can use interpolation and a BorelCantelli argument to prove Theorem 1.

Still, a cleaner proof of a more precise result can be obtained by using a martingale argument to bound the fourth central moments E(Sn _ S~)4 . The latter approach avoids the interpolation argument, and, more pointedly, it provides for socalled complete convergence, rather than just almost sure convergence (see, e.g, Stout, 1974, or Steele, 1981b, for a discussion of the benefits of complete convergence in the context of probabilistic algorithms and of its difference from almost sure convergence).

We recall that a sequence of random variables di, 1 i n, is called a martingale difference sequence provided there is a sequence of sigma fields Fi, 1 i n, such that Fi c F,,, where di is measurable with respect to F,, and E (di 1 Fi,) = 0. The martingale differences we use are defined by

di=E(S,,1Fi)E(S.1Fi~), 1in, (5.1)

where for 1 i n we take Fi to be the sigma field generated by {X., X2,. .., XL and where FO is the trivial sigma field. Since E (Sn ~ Fn) = Sn and E (Sn 1 FO) = s,, the telescoping sum of (5.1) lets us express S. s. in terms of the di,

n

Sn _S~ di. (5.2)

Although it is not particularly easy to compute with the di, they can be made more tractable by introducing some new variables. We let Sn denote the length of the minimal semimatching of the sample with the ith point left out, i.e., S'n = S(Xl, X2,.. ., X1, Xi+l,..., Xn). One benefit of these variables is that E(S'n1Fi) = E (S'n 1 Fi ,), and thus we have

di = E (S. S'n 1 Fi). (5.3)

The critical point is that each expectation in (5.3) is well adapted to analysis by means of Lemmas 2 and 4. In fact, by (5.3) and Jensen's inequality, we have for each p 1 that

Idi1P E(JS, S'n1P1Fi), so taking expectations and using (4.10) gives

ildilip 2ad(pIn ) Ild, (5.4)

where ad, the constant of Lemma 4, depends only on d.

Now, for any martingale difference sequence, Burkholder's square function inequality (Burkholder, 1973, or Chow and Teicher, 1978, p. 384) tells us for p > 1 that

n n 1/2

di 18pq' /2 d 2

1 i

p 11 ( i = 1 ) 11 p

i

i

J. M. Steele / Random semimatchings

where I lp+llq= 1. For p= 4, we find

)4_ 2

E (1~ di _ cE d 2

i

where c 3 6 .2 16 . By expanding this last sum and applying H51der's inequality, we find from (5.4) that

( i n )4 " 4 2 2

E di cE di+2cE didj

1 i<,1 n

n

4

cE 1 di+2

i=1

Kdn 24/d

4)1/2 4)1/2

(Ed 1 (Edl

139

(5.5)

for a constant Kd depending only on d. By Markov's inequality, we then have for any e > 0 that

P(IS,, s, 1 en (d 1)l d)__ '4 Kdn 2. (5.6)

(di)/d

Thus, the probabilities in (5.6) are summable for each s > 0, and since s,, cin this summability is exactly the condition of complete convergence of sn'Sn to the constant Cd. Since the BorelCantelli lemma tells us complete convergence implies almost sure convergence, the proof of Theorem 1 is complete. E]

6. Large deviations

1~

In Section 5 we gave the quickest and cleanest route to the completion of the proof of Theorem 1. More was proved than was needed complete convergence instead of almost sure convergence but the stronger result was obtained largely because it came for free. The purpose of this section is to show how martingale theory can be used to obtain much stronger bounds on the tail probabilities of S. s,, than we found in (5.6).

We continue to exploit the representation (5.2) and, in particular, it will be used together with a recent martingale inequality to prove the exponential tail bound:

P(IS, s. 1 t) A exp( _Bdt2d1(2+d )n (2d)1(2+d) ), 1n<00, 0

where A = e and Bd is a constant that depends only on the dimension d.

Inequality (6.1) is powerful in any dimension d 2, but it is especially convenient for d= 2. In that case, (6.1) reduces to an ordinary exponential bound that is independent of n. Also, on multiplying (6.1) by pt' and integrating, we find by standard bounds on F(p) that when d = 2 all the central moments of S. are bounded independently of n, i.e.,

11 Sn S. 11, JOA

where 8 is a universal constant.

i

i

i

1

1

(6.2)

140 J.M. Steele / Rwidoin seiniinatchings

We can also exploit (6. 1) in another direction to get a rate result for Theorem 1 For example, when d =2 and we take t=2 log nI B,,, then (6.1) leads to a summable bound on the tail probabilities. By the BorelCantelli lemma, we then have a qualitative refinement of Theorem 1:

& = s,, + 0(log n) (6.3)

with probability one. One should note, however, that we cannot replace s,, with C2n 1/2 in (6.3), since we have no bound on S,,_ C"n 1/2 that is sharper than o(n' /2 )

We will now show that for any d 2 inequality (6.1) follows easily from the LP bound on di given in (5.4), and a general martingale inequality due to Rhee and Talagrand (1987). The RheeTalagrand inequality states that there is a constant K such that for any martingale difference sequence {di, 1 i n}, and any t 0 we have

P di t) exp( 2~s), (6.4)

provided s 2 and Ks (jj, 2, t 2.

di 2

When we apply our LP bound (5.4) with p = 2s in (6.4), we find

1112, 2 )2/d,

ldi 2 n4ad(2sln (6.5)

n

11 dill 2, t2,

so we have Ks(liIn 2 provided we take

s=K dl(d +2) a d 2d1(d+2 )2 (2d+2)/(d+2) n (2 d )I (d +2) t 2d/ (d +2). (6.6)

For s 2 the bound on the right in (6. 1) is at least one, so if we take & 2 3 K d I (d +2) C, d 2d/(d+2) we have (6.1) for all d2, 1n <00 and 0

The intention of this section is to give just a taste of the analytical possibilities that are opened up by martingale methods. For d = 2, inequality (6. 1) is natural and effective, but even then there are many opportunities for additional development. To see how such analyses have gone forward in the theory of the traveling salesman problem one should consult Rhee and Talagrand (1988), where a bound is given that shows for d = 2 that the tails of the TSP functional are actually subGaussian. It is not known if such bounds hold for d > 2, but some heuristic considerations suggest that in higher dimensions one would no longer have such rapid decrease of the tail probabilities.

7. Extension to general distributions

The extension of the limit theory of S. from the uniform case of Theorem 1 to the general case of Theorem 2 rests on the fact that there is a class of probability measures that is rich enough to approximate any probability measure with support in [0, 1]d, yet constrained enough to permit a localized application of Theorem 1.

i

1M. Steele / Random sernimatchings 141

These are probability measures on [0, If' with the form g(x) dx+d~l, where (1) g (x) =jail Q,, form" congruent disjoint cubes Qi with edges parallel to the axes,

and (2) the measure ~t, is purely singular (i.e., ~t,([0, 1]d) = ~c,,(A) for a measurable set A of Lebesgue measure zero). These probability measures the socalled blocked distributions were used by Beardwood et al. (1959); and since the beginning of the subject, they have remained a regular feature of extension arguments for subadditive Euclidean functionals.

It should be clear that if a functional 5 is smooth in an appropriate sense then one can carry asymptotic results for the class of blocked distributions to the class of probability measures with bounded support. The following result from Steele (1988) points out a simple continuity condition that suffices.

Theorem. Suppose Z is a measurable realvalued function on the finite subsets of [0, 1 ]", and suppose that there is a constant K not depending on n such that Z satisfies the continuity condition

(d 1)1d

IZ(Xl, X2 1 Xn) Z(X'l, X2', x,'J1 K l{i: xi 5.~ xi}l (7.1)

Further, suppose thatfor every sequence of Li.d. random variables {Xi},,i<~ distributed with a a blocked distribution ~L = ~L, + g(x) dx we have with probability one that

Z(Xl, X2,..., Xn) cdn (dl)ld f g(X)(d1)1d dx. (7.2)

One then has that with probability one,

Z(X', X X) c,n (dl)ld f(X)(dl)ld dx (7.3)

2 n f

whenever {X'i} are independent and identically distributed with respect to anyprobability measure on [0, 1]d with an absolutely continuous part given by f(x) dx. C]

It is easy to justify (7.1) for the semimatching functional. If A

{X[, X2, X2,. Xn} and B = {x,, x2,. . . , x',} then by (2.11) we have

IS(A) S(A n B)l 21 +11d d 1/2 k 11d

~A,81

11d 1/2 11d

21 d 1 k (7.4)

i k j

where j = JAI JA n B1. Applying the same considerations to S(B) S(A n B) and

adding that bound to (7.4), we find for j = JA u BI JA n BI = l{i: Xi 0 X,~}1 that

I S(A) S(B)l 2 2+1/d d 1/2 1 k_ 11d. (7.5)

l~kj

Finally, (7.1) follows from (7.5) by standard estimates.

To complete the sketch of Theorem 2 we need to indicate why (7.2) holds for blocked distributions. We first consider the purely singular case. We let A denote

1

i i

i i

142

1 M. Steele / Randorn semimatchings

the support of ~i,, and let e > 0 be given. We then divide [0, 1]d into m" cells Q such that m' is smaller than e, and a small percentage of the Qi contain almost all of the mass of ~c,. Specifically, since A has Lebesgue measure zero, we can find an m and a subset J c {1, 2, ..m"} such that

m 1 ~2 E,

IJI Emd,

and

~,, ((iu Qi :~: 8.

ei' )')

Now, by the usual feasibility considerations we have

SM 1 S(Q) + S U qi

icj Gi ),

(7.6a)

(7.6b)

(7.6c)

(7.7)

so we only need bounds on the respective sums. By (2.10) any k points in [0, fl,' have a semimatching bounded by M'I'k Id111d; so by scaling we see that if k, is the number of points of {Xj: 1 j n} in Qi then IS(Q)l 8d 112M 'I ki 1(dl)ld.

By H61der's inequality we find

Id

1 S(Qi)_1j111d 8d 1/2 M'(iI ki)

iEJ rj

1)1d

and by the direct application of (2.10) we have

S(U Qi)8d ./2 ( il ki (dl)ld

ioi Ogi)

~ E Ild 8d 1/2 n (dOld

1 (7.9)

(7.10)

Since g,(Ujj Q) ~ E, the strong law of large numbers applied to (7.10) combines with (7.7) and (7.9) to give us

lim sup n(dl)lds(Q),< 811d 8d 1/2 +8d 112E(dl)ld,

nCO

(7.11)

with probability one. Since e > 0 is arbitrary, we have proved Theorem 1 in the case that ~L is purely singular, i.e., 11,([0, 1]d) = 1.

Now we consider the purely absolutely continuous case, i.e., ~L ([0, 1]d) = 0. We let m be fixed and let Qi, 1 __ j __ Md, be the usual partition. We consider the set E of edges e of S(Q) such that e has endpoints in two different subcells, i.e., e E E if e crosses a boundary aQi for some i. This time, let k, denote the number of points of Qi that are endpoints of an edge in E. We claim that there is a Kd such that

M, m

+K,, m1k~dl)ld

S ( U` Q) 1, S (Qi) S ( U' Q)

(7.12)

i

J. M. Steele / Random semimatchings 143

The proof of (7.12) in complete detail would require repetition of some of the considerations of Section 2, but it essentially follows from the idea that one can build a semimatching on each Qi by taking the edges of the semimatching of

S(U1,11

Q) that are completely interior to Qi together with a set of at most ki edges

112

with length at most m'd ' i.e., the diameter of Q.

To bound the sum of the ki, we bound the cardinality of E. The key observation is that for each e E E we either have 1 el > x, or else an endpoint of e is within x of some aQi. Thus, if v,(x) is the number of edges in a minimal semimatching of {Xi : 1 i n} that have length at least x, and n, (x) is the number of points of {Xi: 1 i n} that are within x of aQi for some i, then

ki 2 P, (x) + nn (X). (7.13)

Since XPn (X) is bounded by Sn, Lemma 3 and H61der's inequality tell us that we have

~d 1 (dl)ld

m' k~dl)ld.< ki

(2x18d 1/2 n (dl)ld + nn (X))(d1)1d. (7.14)

When we set x = n ' /d2 a standard analysis of the right hand side of (7.14) shows it is o(n W1)1d ) with probability one. Returning to (7.12), we find

~d ~d

S U Qi 1 S(Q) o(n (dl)ld

c=1 i=l

with probability one. Since the asymptotic behavior of S(Q) is determined by Theorem 1, we have completed the proof of Theorem 2 under the assumption of absolute continuity. The proof for mixed distributions follows from the consideration of the two pure cases and standard probabilistic arguments, so those details are safely omitted.

We have thus completed our sketch of the proof of (7.2). By the continuity theorem, the proof of Theorem 2 is complete. E

8. Concluding remarks

The theory developed here brings together two streams of thought that have their origin in the theory of the traveling salesman problem. First, it is widely recognized that one of the most powerful thrusts in contemporary combinatorial optimization is the algorithmic exploitation of the geometry of special polytopes. This point is forcefully made in Crowderand Padberg (1980), Gr8tschel, (1981,1982), and Lovdsz and Plummer (1986). Second, for many purposes especially probabilistic algorithms and the probabilistic analysis of heuristics there seems to be a sustained

144 J. M. Steele / Random semimatchings

contribution to be made by the theory of subadditive Euclidean functionals that has grown out of the work of Beardwood et al. (1959), Karp (1977), Papdimitriou (1977) and Steele (1981a).

The semimatching problem arises as the simplest part of Edmonds'early program to understand the matching polytope, and thus it has a special historical distinction. Its claim on our attention is further strengthened by the fruitfulness of Edmonds' conception as developed in the investigations of Padberg and Rao (1982), Gr6tschel (1977) and Gr6tschel and Holland (1985, 1987).

The semimatching problem is also the first problem to be brought into the theory of subadditive Euclidean functionals that has its origin within the framework of linear programming. To be sure, the availability of a second geometrical interpretation made the development of the probability theory of semimatching more natural than one would have otherwise expected. Still, the geometry of semimatching is not so simple that its asymptotic theory can be obtained by offtheshelf tools. The failure of the semimatching functional to be monotone lead us to a natural extension of the theory of subadditive Euclidean functionals and, in fact, the continuity established in Lemma 4 turned out to be a condition that is in some respects even more effective than monotonicity.

Of the problems that are left unresolved by the present analysis, the most obvious ones are the determination Of Cd and the possibility of a central limit theorem. There is no subadditive Euelidean functional for which these issues have been resolved; and, despite the fact that semimatching are in some ways very well behaved, there is little hope for quick progress on these problems.

A more promising line of development lies in the direction of general weight functions. The present analysis for w, = 1x yi can be extended to w, = 1X YJ', for 0 < a < d, but it does not seem easy to deal with a = d. In that case, a natural conjecture is that with probability one we have

lim min 1 1 e 1d =C> 0, (8.1)

n~ S eES

where the minimum is over all semimatchings of {Xi, 1 i n} and the Xi are independent and uniformly distributed on [0, ]d . The conjecture (8.1) is analogous to a conjecture of R. Bland on minimal spanning trees (MSTs). Bland's conjecture came about from empirical observation of simulation experiments. Its validity has been recently established by David Aldous and the author. The limit (8.1) still offers considerable technical challenge because semimatchings cannot be obtained via a greedy algorithm, and it is that feature of the MST that proved to be essential in the resolution of Bland's conjecture.

A more conceptual shift is created when one changes to w. = d (x, y) where d is a nonEuclidean distance. Sharp geometrical facts still abound, and the investigation offers reasonable hope. Nevertheless, the subtlety of tilings that might serve in the same role as Qi raises many new issues, and the development of results analogous to Theorem 1 seems to call for a new approach.

J.M. Steele / Random semimatchings 145

Acknowledgement

1 would like to thank John Mitchell for telling me about the geometric nature of (1.1), and for providing the references to the work of Gr~tschel and Holland. 1 also

thank Michel Goemans for comments on an earlier draft.

References

M.L. Balinski, "Integer programming: methods, uses, and computation," Management Science 12 (1965) 253313.

J. Beardwood, J.H. Halton and J.M. Harnmersley,Theshortest path through many points," Cambridge Philosophical Society.. Proceedings 55 (1959) 299327.

L. Burkholder, "Distribution function inequalities for martingales: The 1971 Wald Memorial Lectures," Annals of Probability 1 (1973) 19~42.

Y.S. Chow and H. Teicher, Probability Theory: Independence Interchangeability Martingales (Springer, New York, 1978).

V. Chvdtal, Linear Programming (Freeman, New York, 1983).

H. Crowder and M.W. Padberg, "Solving largescale symmetric travelling salesman problems, "Management Science 26 (1980) 495509.

J. Edmonds, "Matching and a polyhedron with 01 vertices," Journal of Research of the National Bureau of Standards 69B (1965a) 125130.

J. Edmonds, "Paths, trees and flowers," Canadian Journal of Mathematics 17 (1965b) 449467.

J. Edmonds, "Submodular functions, matroids and certain polyhedra," in: Combinatorial Structures and Their Applications (Gordon and Breach, New York, 1970).

B. Efron and C. Stein, "The jackknife estimate of variance," Annals of Statistics 9 (1981) 586596.

M. Grbtschel, Polyedrische Charakterisierungen kornbinatorischer Optimierungsprobleme (Hain, Meisenheim, 1977).

M. Gr6tschel, "Developments in combinatorial optimization," in: W. Jdger, J. Moser and R. Remmert, eds., Perspectives in Mathematics, Anniversary of Oberwolfach 1981 (Birkhduser, Basel, 1981) pp. 249294.

M. CriStschel, "Approaches to hard combinatorial optimization problems," in: B. Korte, ed., Modern Applied Mathematics Optimization and Operations Research (NorthHolland, Amsterdam, 1982) pp. 2239.

M. Gr6tschel and 0. Holland, "Solving matching problems with linear programming," Mathematical Programming 33 (1985) 243259.

M. Gr6tschel and 0. Holland, "A cutting plane algorithm for minimum perfect 2matchings," Computing 39 (1987) 327344.

G.H. Hardy, Divergent Series (Oxford Press, Oxford, 1949).

R.M. Karp, "Probabilistic analysis of partitioning algorithms for the traveling salesman problem in the plane," Mathematics ofOperations Research 2 (1977) 209224.

R.M. Karp and LM. Steele, "Probabilistic analysis of heuristics," in: E.L. Lawler et al., eds., The Traveling Salesman Problem: A Guided tour of Combinatorial Optimization (Wiley, New York, 1985) pp. 181206.

L. Lovdsz and M.D. Plummer, Matching Theory (Adad6rfiiai Kiad6, Budapest, 1986).

M.W Padberg and M.R. Rao, "Odd minimum cutsets and bmatchings," Mathematics of Operations Research 7 (1982) 6780.

C.H. Papadimitriou, "The probabilistic analysis of matching heuristics," Fifteenth Annual Allerton Conference on Communication, Control and Computing (1977) pp. 368378.

W.T. Rhee and M. Talagrand, "Martingale inequalities, interpolations and NPcomplete problems," to appear in: Mathematics of Operations Research.

W.T. Rhee and M. Talagrand, "A sharp deviation inequality for the stochastic traveling salesman problem," Annals of Probability 17 (1989) 18.

1

146 J.M. Steele /Random semimatchings

LM. Steele, "Subadditive Euelidean functionals and nonlinear growth in geometric probability, Annals

ofProbability 9 (1981a) 365376.

J.M. Steele, "Complete convergence of short paths and Karp's algorithm for the TSP, Mathematics of

Operations Research 6 (1981b) 374378.

LM. Steele, Growth rates of Euelidean minimal spanning trees with power weighted edges," Annals

ofProbability 16 (1988) 17671787.

LM. Steele, L.A. Shepp and WT. Eddy,Onthe number of leaves of a Euclidean minimal spanning

tree," Journal ofApplied Probability 24 (1987) 809826.

W. Stout, Almost Sure Convergence, Journal ofApplied Probability (Wiley, New York, 1976).

V,A. Yemelichev, M.M. Kovalev and M.K. Kraytsov, Polytopes, Graphs, and Optimization (Cambridge

University Press, New York, 1984).

1