Please see PDF version
MATHEMATICS OF OPERATIONS RESEARCH Vol. 6, No. 3, August 1981 Printed in U. S.A.
COMPLETE CONVERGENCE OF SHORT PATHS AND
KARP'S ALGORITHM FOR THE TSP*t
J. MICHAEL STEELE
Stanford University
Let X,, 1 Q i < oo, be uniformly distributed in [0, 112 and let Tn be the length of the shortest closed path connecting (X,, X2, X,}. It is proved that there is a constant 0 < 8 < 00 such that for all E > 0
P Tn < 00.
n=l
This result is essential in justifying Karp's algorithm for the traveling salesman problem under the independent model, and it settles a question posed by B. W. Weide.
1. Introduction. The main objective of the present note is to solve a problem proposed by Weide (1978) concerning the complete convergence of certain random variables associated with Karp's probabilistic analysis of the traveling salesman problem (Karp (1976), (1977)).
To set the problem precisely let Xi, 1 < i < oo, be independent random variables uniformly distributed on the unit square [0, 112 , and let T,, denote the length of the shortest closed path (in the usual Euclidean distance) which connects each element of (Xl, X2, . . . , X,}.
It was proved by Beardwood, Halton, and Hammersley (1959) that
lim TJFn = 8 n >oo
with probability one for a finite constant P. This fact was central to the motivation behind Karp's algorithm, but as Weide (1978) points out the Karp algorithm actually calls for the following stronger result to be proved here:
THEOREM 1. There is a constant 8 such that for all E > 0, one has
00
2: P (1 T, / Fn P 1 > c) < oc. n l
This type of convergence is usually called complete convergence, and Theorem 1 stands in a similar relation to the Beardwood Halton Hammersley Theorem as the Hsu Robbins Theorem stands in relation to the strong law of large numbers (Lukacs (1968), Hsu and Robbins (1947)). The "easy half" of the Borel Cantelli lemma shows that Theorem 1 implies the Beardwood Halton Hammersley Theorem and the "hardhalf" of the Borel Cantelli lemma shows how Theorem 1 is necessary in modeling contexts where problems of increased size are generated independently of previous problems. (For a full discussion of independent versus incrementing models for random problems one should consult Weide (1978).)
By an elementary lemma due to Few (1955) the variables TJFn are bounded, so the almost sure convergence in the Beardwood Halton Hammersley Theorem neces
*Received August 21, 1979; revised May 15, 1980.
A MS 1980 subject classification. Primary 601)05, Secondary 90C42.
ORIMS Index 1978 subject classification. Primary: 491 Networks/graphs traveling salesman.
Key words. Traveling salesman problem, complete convergence, subadditive processes, subadditive Euclidcan functionals, jackknife, Efron Stein inequality.
t Research supported in part by Office of Naval Research Grant NOOO 14 76 C 0475.
374 0364 765X/81/0603/0374$01.25
Copyright 0 1981, The institute of Management SLiences
COMPLETE CONVERGENCE OF SHORT PATHS 375
sarily entails ET, flFn as well. This fact, Markov's inequality, and a standard 2E argument show that Theorem 1 is an easy consequence of the following result.
THEOREm 2. For all k > 0 there is a constant c, such that
E(T~ ETn)'< c, (1,
for all n >, 1.
Actually for Theorem 1 it would suffice to show (1. 1) for any k > 2, but the present method extends without effort to give the full result. The proof of Theorem 2 is based upon a systematic recursive application of a recent jackknife inequality due to Efron and Stein (1978). This inequality is described in the next section. The third section gives the proof of Theorem 2, and the last section touches briefly on some extensions of these results.
2. Two inequalities. If S(X11X21 ... 1 Xn ) is any symmetric function of n 1 vectors xi, and Xi are independent identically distributed random vectors we define new random variables by
Si = S(Xl 1 X21 ... 1 X, IIXi+11 .... Xn)
and
S. n
n si.
Efron and Stein (1978) proved the following inequality
n
Var S(Xl, X2, . . . , Xn 1) < E (Si S.)2.
This remarkable inequality will no doubt find many applications in the asymptotic analysis of nonlinear processes. By its application in the present case it was possible to both simplify and sharpen an earlier proof of Theorem 1 due to the author. The earlier proof was based on the theory of independent subadditive processes.
The second inequality concerns the variable d,, = min Xi X, 1 < i 4 n} where [0,112.
Xi are independent and uniformly distributed in It is that for all k > 0 there is a
constant Ak such that
Ed,,k <~A,n k12 foralin. (2.2)
The proof of (2.2) is easy. One just notes by geometry that P(d,, > x) ~Q (1 aX2) even with a = 7r14. Then by generous bounds,
Ek ~Q k 1 aX2(n~l)dX,~ A n k12.
d,'fo 00 X e k
3. Proof of Theorem 3. The proof of Theorem 3 can now be given. By the Efron Stein inequality applied to S= O(Tn where 0 is a smooth function one obtains
Var O(T, E (oi 0.)2 (3.1)
where opi =.O(T(Xl,X2, Xi 1jj+1, X.) and (I/n)l:" toi. Replacing
by any other function of X,, X2, X,, only increases the right side of (3. 1), so we
have
n
Var 0( T,, s~ E T, 2 (3.2)
376 J. MICHAEL STEELE
By the mean value theorem it is possible to choose a value T'_,(i) between
T(Xl, X2, Xi 1, Xi, 1, Xj and T(X,, X21 ... 1 Xn 1) SUCh that
Oi O(T', 1) 0'(T. 1(i))An(i) (3.3)
where An (i) T(Xl 1 X2, . ~ xi 1, xi+ 1 * * j Xn) Tn 1. Applying the representa
tion (3.3) to (3.2) and using the identical distribution of the Xi's will yield
Varo(T,,_,) <, nE(O'(T,, 1('))An( 1))2. (3.4)
We will now make some special choices of 0 and proceed inductively. First consider simply 0(x) = x, then (3.4) becomes
Var T,, (A2( 1)) < 2A
1 < nE n 2
where A 2 is the constant provided by inequality (2.2) since 1 An 1 < dn Next, choose 0(x) = (x ETn 1)2 and apply Schwarz' inequality to (3.4) to obtain
Va* T, 1 ET,, 1)2) < nE((2(T,, ,(1) ET~ )An(j))2)
<, 22n(E(T,,_,(1) ETn 1)4)112 (EI,( 1)4)112.(3.6)
Now since (a + b)4 < 16(a 4 + b 4) we have
1)4) < T', ET,,_ 1)4)
E((T,1(1) ET,,_ 16E(T,,_1(1) 1)4 + 16E((T,,_ 1
<, 16EA4(1) + 16E(T,, , ET,,_ 1)4. n
Applying 1An (Q ~ dn and (2.2) the last inequality reads
E((T._1(1) ET,,_ 1)4) 1,~ 16E(Tn_ I ~ ET,,_ )4+ 16A 1) 2.
4(n
But since
Va*Tn~l ET, 1)2) E(Tn_l ET._1 )4 _ (E(T,, , ET._.)2)'
E(Tn_ I ETn 1)4 _ (Var T,, 1)2 equations (3.5) and (3.6) imply
1)4 1)4
E(Tn_ I ETn < 4A' + 22n (16E(T,, ET,,
2
2) 2A41/2
6A4(n I) (n 1) '. (3.7)
+
)4)1/2
Dividing both sides of (3.7) by (E(T,, E1n is good enough to show that
1)4
E(1n ET,, is bounded by a constant which is independent of n > 2. This proves the theorem for k = 4, and this special case has been done in such detail because the case k = 4 is sufficient to prove Theorem 1.
The proof of the general case will be by induction. We begin by supposing the y Jensen's inequality and the existence of ck and proceed to show the existence of C2k. induction principle, this will complete the proof. In order to avoid concerning ourselves with irrelevant constants the Vinogradov symbol an << bn will be used to indicate that there is a constant c not depending on n such that an Q cb,, for all n sufficiently large.
1)k
This time we take ~5(x) = (x ET,,_ and apply (3.4) to obtain
1)k 1An(j))2
Var O(Tn << nEQTn (1) ETn
1)k 1))2. (3.8)
<< nE((T, 1 ET,._ 'An(
COMPLETE CONVERGENCE OF SHORT PATHS 377
Applying Hblders inequality with p = 2k/2(k 1) and q = k one obtains
Varo(Tn_ 1) << n(E((T,,_ , ET,,_ 1)2k)) 2(k I)/2k (EAn(l) 2k)11k.
By inequality (2.2) we can check that EA2k(l) << n k SO
2k 2(k I)/2k
Var O(T. << (E((Tn ET,~ 1) )) (3.9)
Since Var O(T,, 1) = E((Tn 1 ET~ 1)2k) (E(T~ , ETn )k)2 the induction assumption and (3.9) imply
E((T,, , ET,,_ 1)2k) << Ck2 + (E(T,, 1 ET~ 1)2k)2(k I)/2k. (3.10)
Now just as in (3.7) the presence of the small power on the right side leads to a uniform bound on E(Tn , ET~ 1)2k and thus proves the existence Of C2k. As mentioned at the beginning, this suffices to complete the proof.
4. Further results. In the previous section the aim was to give the most direct proof possible of the result conjectured by Weide (1978). There are many natural extensions of that result, and some of those will be stated here. The proofs of these results can be given along exactly the same lines used in §3. The most obvious extension is the following.
THEOREM 3. Suppose (Xi) are independent and uniformly distributed in [0, 11 d and T,, = T(Xl, X2, . . , Xn) is the length of the shortest closed path through {X,, X21 .... XJ, then
E(T,, ET,, )k< ckn (k/2)(1 d/2) for some ck and all n > 1 (4.1)
and
00
E P(ITnIn (d 1) 1d 1 > E) < 00 for some 0 and all E > 0. (4.2)
n 1
In Theorem 3 one might also seek to replace the functional T, by other Euclidean functionals for which the analogue of the Beardwood Halton Hammersley Theorem is known. The analogue of Theorem 3 does hold for the Steiner tree problem and the rectilinear Steiner tree problem. The proof in these cases differs little from that of §3. It is not known at present if the full analogue of Theorem 3 is valid for the whole class of Subadditive Euclidean Functionals (Steele (1979)).
As a final point one should note that both Beardwood Halton, and Hanintersley (1959) and Steele (1979) contain results valid for random variables with nortuniform distributions. The approximation processes used in these papers to extend the uniform case can again be tried here although to do so would require considerable space. Since the algorithmic applications initiated by Karp (1976), (1977) are already ably served by Theorem 1, these nonuniform extensions are not pursued here.
References
[11 Beardwood, L, Halton, J. H. and Hammersley, J. M. (1959). The Shortest Path through Many Points. Proc. Cambridge Philos. Soc. 55 299 327.
[21 Efron, B. and Stein, C. (1978). The Jackknife Estimate of Variance. Technical Report No. 120, Department of Statistics, Stanford University.
[31 Few, L. (1955). The Shortest Path and Shortest Road through n Points. Mathematika 2 141 144.
[4] Hsu, P. L. and Robbins, H. (1947). Complete Convergence and the Law of Large Numbers. Proc. Nat. Acad. Sci. U.S.A. 33 25 31.
378 J. MICHAEL STEELE
[51 Karp, R. M. (1976) . The Probabilistic Analysis of Some Combinatorial Search Algorithms. Algorithms and Complexity: New Directions and Recent Results. J. F. Taub, ed. Academic Press, New York, pp. 1 19.
[61 (1977). Probabilistic Analysis of Partitioning Algorithms for the Traveling Salesman Problem in the Plane. Math Oper. Res. 2 209 224.
[71 Lukacs, E. (1968). Stochastic Convergence. D. C. Heath and Co., Lexington, Mass. 48 49.
[81 Steele, J. M. (1979). Subadditive Euclidean Functionals and Non Linear Growth in Geometric Probability. Technical Report, Department of Statistics, Stanford University (to appear in Ann. Probability).
[9] Weide, B. W. (1978). Statistical Methods in Algorithm Design and Analysis. Thesis, Department of Computer Science, Carnegie Mellon University.
DEPARTMENT OF STATISTICS, STANFORD UNIVERSITY, STANFORD, CALIFORNIA 94305