Please see PDF version
Mathematical Programming 53 (1992) 127 146 127
North Holland
Euclidean semi matchings 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 semi matching. The main result is the determination of the asymptotic behavior of the length of the minimal serni matching. 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 non random Euclidean semi matchings and large deviation inequalities for random semi matchings 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 well known 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 well known result of Balinski (1965) tells us that if G is the complete graph K,, then there is a solution of (1. 1) in semi integers, 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 #13MS 8812868, ARO contract DAAL03 89 G 0092.POOI, AFOSR 89 08301.A and NSA MDA 904 89 2034.
128 J. M. Steele / Randoin serni matchings
program (1.1) will be called the semi matching 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 2 factors. One can also find a discussion of the semi integer 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 semi matchings 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 semi matching and ordinary matchings. One modest difference that nevertheless makes semi matchings 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 semi matchings 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 seini matchings 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 semi matching of {V, V,..., Vj. For any d 2, there is a constant Cd > 0 such that
liM SnIn (d l)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 semi matchings, 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 semi matching functional S is also well behaved 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 (d l)ld = C, fR f(X)(d 111d dx. (1.3)
n w 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 non probabilistic insights, and thus much of the work of this paper is non probabilistic. In particular, the next section provides three geometric inequalities that serve to articulate the structural parallels between semi matching 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 semi matchings. 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 semi matchings
The two geometric properties that contribute the most to the asymptotic analysis of the minimal Euclidean semi matching are the following: (1) the subadditivity
130 1M. Steele / Random semi matchings
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 semi matching 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 semi matching 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 semi matchings of Qi n {v,, v,,. . . , v,} provides a
feasible semi matching 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 semi matching 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 semi matchings
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 semi matching 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 semi matching for {VI, V2, V,} that has cost bounded by S(V1 , V2, . . . , Vn+l).
i
1
132 JM. Meele / Random semi matchings
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
lz wl+lz w'i 21z wl+lw w'l and lz wl 1v,+, 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 semi matchings 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 (d l)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 1 j _ 1 11d
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,. ~j 1, Vj+1, V0 and
continuing successively, we find
S(V1, V2, Vn)
n
21+ 11d d 1/2 1 j 11d ~2 (d+l)ld d 3/2 (d 1) 1n (d l)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 semi matchings and the traveling salesman problem. This connection can be made most explicit by laying out some of the abstract properties of the semi matching functional that connect semi matchings 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 semi matchings
(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, semi matchings 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) + CtMd 1, (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 semi matchings 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 semi matchings 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 semi matchings 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) Md l
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', m 1. (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 m a' 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 ~ A 0
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)=e A 1 s,A"In! cA'. (4.9)
n=0
i
i
136 J.M. Steele /Random serni matchings
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 2 d(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
n ihi k
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,
(d l)ld
s, cdn (4.14)
J. M. Steele / Random senfl matchings 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: lk A 1 ' A3/5
+0 Y" A 3/5 A "d e "A k 1M
Glk A I
= S, + 0(exp( A 1/6 /2)) + O(A
Since P(A)= CA Id 1)1d + o(A Id 111d ) by (4.9), we thus have s, = cA (d Old + 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 cn 11d. n
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 one sided bounds, the Tauberian arguments retain some benefits; but, where one has two sided 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
(d l)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 semi matchings
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 1 21d). With such a bound on Var(Sn), one can use interpolation and a Borel Cantelli 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 so called 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 ~), 1 i n, (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 semi matching of the sample with the ith point left out, i.e., S'n = S(Xl, X2,.. ., X 1, 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 semi matchings
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 2 4/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)
(d i)/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 Borel Cantelli 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 (2 d)1(2+d) ), 1 n<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 seini inatchings
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 Borel Cantelli 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 Rhee Talagrand 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(li In 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 d 2, 1 n <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 sub Gaussian. 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 serni matchings 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 so called 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 real valued 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 (d l)ld f g(X)(d 1)1d dx. (7.2)
One then has that with probability one,
Z(X', X X) c,n (d l)ld f(X)(d l)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 semi matching 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~k j
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 semi matchings
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 semi matching bounded by M'I'k Id 111d; 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(d l)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 (d l)ld
ioi Ogi)
~ E Ild 8d 1/2 n (d Old
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 (d l)lds(Q),< 811d 8d 1/2 +8d 112E(d l)ld,
n CO
(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,, m 1k~d l)ld
S ( U` Q) 1, S (Qi) S ( U' Q)
(7.12)
i
J. M. Steele / Random semi matchings 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 semi matching on each Qi by taking the edges of the semi matching 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 semi matching 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 (d l)ld
m ' k~d l)ld.< ki
(2x 18d 1/2 n (d l)ld + nn (X))(d 1)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 W 1)1d ) with probability one. Returning to (7.12), we find
~d ~d
S U Qi 1 S(Q) o(n (d l)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 semi matchings
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 semi matching 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 semi matching 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 semi matching more natural than one would have otherwise expected. Still, the geometry of semi matching is not so simple that its asymptotic theory can be obtained by off the shelf tools. The failure of the semi matching 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 semi matching 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 semi matchings 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 semi matchings 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 non Euclidean 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 semi matchings 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) 253 313.
J. Beardwood, J.H. Halton and J.M. Harnmersley, Theshortest path through many points," Cambridge Philosophical Society.. Proceedings 55 (1959) 299 327.
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 large scale symmetric travelling salesman problems, "Management Science 26 (1980) 495 509.
J. Edmonds, "Matching and a polyhedron with 0 1 vertices," Journal of Research of the National Bureau of Standards 69B (1965a) 125 130.
J. Edmonds, "Paths, trees and flowers," Canadian Journal of Mathematics 17 (1965b) 449 467.
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) 586 596.
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. 249 294.
M. CriStschel, "Approaches to hard combinatorial optimization problems," in: B. Korte, ed., Modern Applied Mathematics Optimization and Operations Research (North Holland, Amsterdam, 1982) pp. 22 39.
M. Gr6tschel and 0. Holland, "Solving matching problems with linear programming," Mathematical Programming 33 (1985) 243 259.
M. Gr6tschel and 0. Holland, "A cutting plane algorithm for minimum perfect 2 matchings," Computing 39 (1987) 327 344.
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) 209 224.
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. 181 206.
L. Lovdsz and M.D. Plummer, Matching Theory (Adad6rfiiai Kiad6, Budapest, 1986).
M.W Padberg and M.R. Rao, "Odd minimum cut sets and b matchings," Mathematics of Operations Research 7 (1982) 67 80.
C.H. Papadimitriou, "The probabilistic analysis of matching heuristics," Fifteenth Annual Allerton Conference on Communication, Control and Computing (1977) pp. 368 378.
W.T. Rhee and M. Talagrand, "Martingale inequalities, interpolations and NP complete 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) 1 8.
1
146 J.M. Steele /Random semi matchings
LM. Steele, "Subadditive Euelidean functionals and non linear growth in geometric probability, Annals
ofProbability 9 (1981a) 365 376.
J.M. Steele, "Complete convergence of short paths and Karp's algorithm for the TSP, Mathematics of
Operations Research 6 (1981b) 374 378.
LM. Steele, Growth rates of Euelidean minimal spanning trees with power weighted edges," Annals
ofProbability 16 (1988) 1767 1787.
LM. Steele, L.A. Shepp and WT. Eddy, Onthe number of leaves of a Euclidean minimal spanning
tree," Journal ofApplied Probability 24 (1987) 809 826.
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