Please see PDF version
SIAM J. DISCRETE MATH. 1994 Society for Industrial and Applied Mathematics
Vol. 7, No. 2, pp. 314 324, May 1994 018
SUMS OF SQUARES OF EDGE LENGTHS AND SPACEFILLING
CURVE HEURISTICS FOR THE TRAVELING SALESMAN
PROBLEM*
JUN GA0t AND J. MICHAEL STEELEt
Abstract. The sum of squares of the edge lengths of the tour provided by the spacefilling curve heuristic applied to a random sample of n points from the unit square is proved to be asymptotically equal to a periodic function of the logarithm of the sample size.
Key words. spacefilling curves, traveling salesman problem (TSP), minimal spanning tree, combinatorial optimization, order statistics, sums of squares
AMS subject classifications. primary 05C05, secondary 60F15
1. Two sources of motivation. Two lines of investigation come together to form the motivation for the present work. The first of these concerns the behavior of the sums of squares of the edge lengths in several classical problems of geometric combinatorial optimization. The second concerns recent progress in the understanding of the behavior of the spacefilling curve heuristic for the traveling salesman problem (TSP).
Sums of squares of edges. This line begins with an empirical discovery of R. Bland. Since we obtain the same minimum spanning tree (MST) for a set of n points {Xl, X2,. .. , Xn} C [0, 1]2 whether we assign edge costs % that are equal to the Euclidean length iixi xj I I or to the square of the lengths I lX, _ Xj112, we can save some computation time by working with the squared lengths. When Bland used the sum of squared edge lengths as the feature of merit in a study of algorithms for the MST, he found after computing the MST of a number of random samples of different sizes from (0, 112 that the value of the minimum value of the sum of squared edge lengths showed very little dependence on n and little vaxiation between samples. Bland was led to conjecture that there is a constant CMST such that for the MST of {X,, X2,. . ., Xn} where the Xi are independent random variables with the uniform distribution on [0, 112, we have
lim CMST
n~oo
cEMST
with convergence in probability. This conjecture was proved in Aldous and Steele [1]. The method used to prove (1) relied on the possibility of calculating the MST via a greedy algorithm. Still, there are many functionals that are closely related to the MST for which there is no such possibility. Probably the most studied of these is the TSP that asks for the shortest tour through the points {X,, X2, .. , Xn} C [0, 11 2. We do not know at present whether the analogue to (1) holds for the TSP.
For the worst case analysis, the state of knowledge for the TSP is more complete. Snyder and Steele [101 showed that there is a universal constant CTSP such that, for
* Received by the editors November 23, 1992; accepted for publication (in revised form) March 2,1993.
t Portfolio Management International, Swiss Bank Corporation, 10 East 50th Street 32nd floor, New York, New York 10022.
t Department of Statistics, Whaxton School, University of Pennsylvania, Philadelphia, Pennsylvania 19104 (ateeleowharton. upenn. edu). This author's research was supported in part by National Science Foundation grant DMS92 11634 and Army Research Office grant DAAL03 91 G 0110.
314
i
1
SQUARED EDGE LENGTHS AND THE TSP 315
any S ~ {Xl,X2.... ~ Xn} C [0, 1]2 and any tour T of S of minimal length, we have
(2) E 1 jel 12 < CTSp log n.
eET
In subsequent analyses, Bern and Epstein [3] showed that the logarithmic term of (2) could not be replaced with a more slowly growing function.
Limit theory for the spacefilling heuristic. The spacefilling curve heuristic rests on the existence of a surjective mapping 0 : [0, 1] , [0, 112 such that for each X E [0, 1]2 we can quickly compute a t E [0, 11 such that V)(t) = x. Formally, given {Xl,X2, ,Xn} [0, 1]2, we have a three step process where we (1) compute a set of points {tl, t2, .., t,,} C [0, 11 such that 0(ti) = xi for each 1 < i < n, (2) order the ti so that t(l) :~ t(2) :5 ... :5 t(n), and, finally, (3) define a permutation o : [1, n] [1, nj by requiring x,(i) = 0(t(i)). The path that visits {Xl, X2,. .., Xj in the order Of X,(1), Xa(2) 3 ... j Xor(n) will be called the spacefilling curve path, and the tour that closes this path by adding the step from x,(,,) back to x,(,) will be called the spacefilling curve tour.
Here we will focus on the behavior of the spacefilling curve heuristic in the context
of the simplest possible stochastic model, where the points to be toured axe modeled
by independent random variables Xi, 1 < i < n that are uniformly distributed in
[0, 112. In [41, results of Platzman and Bartholdi [8] were refined to show that for a
large class of spacefilling curves (SFCs) the length LsFe = LSFC (X,, X2 X.) of
n
a spaceffiling heuristic tour through {Xl, X2,.. .' X" } satisfies
lim ELSFC
~n
n Vln tp(log,, n)
where p is an integer depending on the geometry of the spacefilling curve and where
(p is a continuous periodic function of period 1 that is bounded away from zero. This
OPT OPT
behavior offers a novel contrast to that of the length Ln =Ln (Xl,X2,...,Xn) of the shortest tour through the random sample {Xl, X2,. .., XQ, where the theorem of Beardwood, Halton, and Hammersley [21 declares that for the optimal solution no periodic term is needed; rather, there is simply a constant ~3 > 0 such that for n oe we have
LOPT/Vrn
n
where the convergence takes place in expectation as well as with probability 1.
The purpose of this article is to provide a precise asymptotic understanding of the
sum of the squares of the edges of the tour provided by the spacefilling curve heuristic
n n
(4) Sn IX,,,(i) Xm(i+l) 11, 1 IIP(t(i)) IP(t(i+l)) 1 l,'
where we invoke the convention that
u(n + 1) 4 ef o,(1) and t(,,+1) clef t(l).
We will establish the possibly surprising fact that for a large class of spacefilling curves the value of this random variable is well approximated by a periodic function of the logarithm of the sample size.
i
1
316 JUN GAO AND J. MICHAEL STEELE
2. Main result. The first three properties described below are found in many classical spacefilling curves, including those of Hilbert [51 and Peano [71. For these and related curves, the ordinary Lipschitz property and the bimeasure preserving property are established in Milne [61. The dilation and translation properties are easily verified by direct consideration of the traditional constructions, and only minor alterations of the usual constructions are needed to obtain curves with the circular Lipschitz property Assumption 4.
Assumption 1 (dilation property). There is an integer p > 2 such that, for all 0 < S,t < 1,
1[0 (PS ) p G) 11
Assumption 2 (translation property). For 1 < i < p, if (i 1)/p :5 s, t < ilp, then
1 l~b(S) ~*) 11 = 1 IIP(s + '/P) 7p(t + '/P) 11
Assumption 3 (bimeasure preserving property) Given any Borel set A in [0, 11, the set ip(A) is measurable, and
,\,(A) = 1\2(iP(A)),
where l\d is the Lebesgue measure on Rd.
Assumption 4 (circular Lipschitz property). There is a constant cp such that
1 IIP(s) 0(011 < COP(S, t)1/2, where p is the circular metric on [0, 1] given by
p(s, t) = minfis tI, 1 is tJ}.
The main result of this article is the following theorem.
THEOREM 1. If a heuristic tour is built using a spacefilling curve ?P that satisfies Assumptions 1 4, then there exists a strictly positive continuous function W of period 1 such that
(5) lim ES, 1,
n oc ~ (lo gpn)
where p is the integer of Assumptions 1 and 2.
3. Convergence of expectations. We first recall that a ?p that satisfies Assumption 3 creates a natural correspondence between random variables with the uniform distribution on [0, 112 and [0, 11. We safely omit the routine proof.
LEMMA 1. Suppose that X is a random variable that is uniformly distributed in [0, 112 and that ?P : [0, 1] ___> [0, 1]2 is a ~jection. Let iP* be a function that, for every X E [0, 11 2, selects a preimage of x; that is, ip* satisfies ~b (ip* (x)) = x. For t defined by t = iP* (X), we have the fact that t is uniformly distributed in [0, 11, provided that the spacefilling curve iP satisfies the bimeasure preserving Assumption 3.
One key to the analysis of Sn is that ESn has a tidy expression in terms of the independent (unordered) ti's. If d(s, t) is given by
d(s, t) t S if 01 s+t if 0
i
i i i i i
SQUARED EDGE LENGTHS AND THE TSP 317
then d(s, t) describes the distance along the circle of unit circumference in the coun
terclockwise direction from s to t, and we can write S, in the symmetrical form
n
S. ~b (ti) V) ((ti + bi) mod 1)112,
where
bi = min d(ti, tj)
tjESi
and Si = {tl,t2, ti 15ti+15 ... ~ tn}. Moreover, the variables 6i and ti are independent, and for each i the variable 6i has probability density given by
f (t) = (n t)n 2;
so we can compute
n
ES, = E 1 l~b (ti) ~b ((ti + 6j) mod 1)112
= nElIV)(ti) Vfflti + 61) mod 1)112
1 1
= n in fo 11~)(s) ip((s + t) mod 1)11'(n 1)(1 _ t)n 'dsdt.
Finally, introducing
M(t) = 10 1 lip(s) 0((s + t) mod 1) I'ds,
we end up with the following lemma.
LEMMA 2 (key representation). It holds that
1
(6) ESn = n(n 1) fo M(t)(1 _ t)n 2dt.
To use this representation, we must collect some properties of m(t). From the definition of m(.) and the circular Lipschitz property (Assumption 4) of 0, we immediately find a useful pointwise bound.
LEMMA 3. For 0 < t < 1, we have
m(t) ::,~ e2~, min(t, 1 t),
where cp is the Lipschitz constant of Assumption 4.
To get to the deeper properties of m(t), we first set q = l lp and define a sequence of related functions Un}nko on the increasing intervals [0,p"q] by
1 t
fo(t) = 10 1 IV,(8 + t) _ lp(S) 112 ds, 0 < t < q
and
fn(t) = pnfo 0 < t < p'q.
pn
( t ) 1
i
1
318 JUN GAO AND J. MICHAEL STEELE
We also define a parallel sequence of functions {gj,,>o by
g(t) = fo (t) + C2
0 ~bt2, 0 < t < q
and
g. (t) = P"gO 0 < t < pnq.
pn
( t ) 1
The benefit of introducing f, and g, is that we can show that they share a common limit that offers insight into the behavior of m(x). We first establish a monotonicity relationship.
LEMMA 4. There is a function w(t) such that for all n > 0 we have
(7) AW :~ f.+1(t) < W(t) < gn+l(t) :S 9.(t),
Proof. For any 0 < x < q, we see from the definition of m(x) that
p ,,q x
(8) m (X) p (S) _ 0 (S + X) 112 dS
Next, by the translation Assumption 2, by changing variables, and by the dilation
Assumption 1, we obtain
p q~x
11,0(8) 0(8 + X) 112 ds =p 1 llp(S) 0(8 +X) 112 ds
f(t l)q fo
(8) (8 + P:,7) j~2 d$
p p
(9) 1 pX
P fo p($ + PX)j12ds
1 M(Px). p
By combining (9) and (8), we find the basic fact that
(10) M(X) ~~ 1 rn(px),
p
and from (10) the first inequality of (7) follows immediately.
Turning to the g.,,, we first note by the definition of go and identity (9) that for
0 < x < q we have
P 1
1 IV)(8) _ ?p(S + X)l 12 E 11,0(8) _ 0(8 + X)jj2 2 2
90(x ds + ds + cX
P 1
M(PX) + q 11,0(8)_0(S+X)i12dS+{C2OPX2 _4(p_l)X2}
p £~3~
P 1
M (P ) + c 2 AT 2 + q 11~p(S) O(S + X)112 ds cox 2
p p £x
i
i
SQUARED EDGE LENGTHS AND THE TSP 319
By the Lipschitz property of ?P, we have
li~b(S)_0(8+X)i12 _C2X2<0;
ds ~p
so, after replacing x by xlp, we have for 0 < x < 1 that go(x) ~~ pgo(xlp), and our inequality for go immediately yields the last inequality of (7).
Local boundedness and monotonicity of the sequences f,' (x) and 9,' (x) tell us the sequences have pointwise limits. The definition of g,, further tells us that
2
(12) g.(X) MX) = c V)X2 lp', 0 < x < p'q;
so, in fact, both f,, (x) and g,, (x) must have the same limit; moreover, if we denote this limit by w(x), then by the first and last inequalities of (7) we have for 0 < x < p'q that
(13) (X) :5 W (X) :5 g. (X),
completing the proof of Lemma 4.
The next lemma shows how w(x) approximates m(x) and articulates a vital scaling property.
LEMMA 5. The function w has the following properties:
(a) W(t) :5 Oot for 0 < t < 1,
(b) For 0 < t < q = 11p, IM(t) W(t) I < C,2
pt2,
(c) w(t) = pw(t/p).
Proof. By Lemma 3, we have m(u) < 4u for 0 < u < 1; so, for 0 < x < pn q we
have
(14) A(X) = p~nm(x,p~,) < pC.1,x/pn = C20,
yielding (a). To show (b), we note that the case where n = 0 in inequality (7) states that, for 0 < x < q,
m (X) = fo (X) < m (X) :5 90 (X), and, by the definition of go, we obtain
IM(X) W(X)l :5 lgo(X) _ fo(X)1 = Cl~,X2,
All that remains is to establish (c). By Lemma 4 and the definition of go, we have
W(X/P) = lim P'M
n oc p. pn
( X )
= lim 1 {pn+1. ( X
n~oo p pn+l
W (X) /P,
completing the proof of the lemma.
LEMMA 6 (first Laplace representation). As n > oc, we ha.ve
1
(15) ESn = n' fo m(t)e n'dt + 0(l/n).
320 JUN GAO AND J. MICHAEL STEELE
Proof. The difierence between ES,, and the integral of (15) is bounded by
f1
m(t)1n2e ,,1 n(n 1)(1 t)n 2 Idt,
and, by Lemma 3, M(t) = Offi as t > 0; so easy estimates give the lemma.
We can modify this last representation slightly to obtain one with the form of a standard Laplace integral. First, we note that
q
ES,, = n 2 fo C ntm(t)dt + n 2 fq e nt m(t)dt + 0(l/n)
= n 2 fq e 'tw(t)dt + 0(l/n),
0
since
fq q
2 n 2 ntC.2
o n e t im(t) w(t) Idt < JO n e bt2 dt = 0(l/n) and
n 2f 1 m(t)e ntdt < n2 1 c20te dt < c.0n2e nq.
q fq
Moreover, we have
00 "a
n2W(t)e n'dt < n 2 c,2p t e ntdt = 0(n 2 e qn
fq
so we have proved the following lemma.
LEMMA 7 (second Laplace representation). It holds that
ES,, = n 2 fo w(t)e ntdt + 0(l/n).
All that remains is to show that the last integral is a periodic function of logp n. If we let I(n) denote the value of the integral, divide the interval [0, oo) into subintervals [p'/n, pk+l /n], where oo < k < oo, and let t = Pk+u /n, then we obtain
00 p k+l/n
I(n) = n 2 1: w(t)e ntdt
k= oo p
(16) 00 1
= n E fo w(p'+u/n)p'+u exp( p"') log pdu.
k= 00
Using the key recursion relation of Lemma 5, part (c), we have w(p'+u/n) = plw(pu/n); so
1 00
I(n) = logp W n) / (P,, 1,., n ) E ~2(k+u) eXp( p k+u )} du
JO {k= oo
= logp {W(pu ,.,n)/C 17,pn)} 1(u)du,
SQUARED EDGE LENGTHS AND THE TSP 321
where 1(u) is defined by
1 (U) p 2(k+u) exp(_pk+u).
k= oo
Since the defining sum for 1 converges uniformly on compact subsets of [0, 00), we see that 1 is continuous. Furthermore, if we define a function W by
(17) W(X) = logpfl
', {W(P IX U,)/(P (X U))} 1(u)du,
0
the continuity of 1, the local boundedness of w, and the convolution form of (17) show that W is also continuous. Since ~o(logp n) = I(n), we can write Lemma 7 as
ES,, = W(logp n) + 0(l/n),
and the proof of the theorem is completed once we establish the following lemma.
LEMMA 8. The function W is continuous, periodic of period 1, and bounded away from zero.
Proof. We have already noted the continuity of W, and periodicity is immediate from the recursion w(pu) = pw(u) combined with the integral representation (17) of W. The integral representation also gives W(x) > 0 for all x.
By compactness, (p will be bounded away from zero unless there is an xO such that W(x0) = 0. However, for such an xO, we would get from (17) that w(p (x. ')) = 0 for all 0 < u < 1. By the recursion w(pu) = pw(u), we could then conclude that both W and ES,, were identically zero. This contradiction establishes that W(x) is bounded away from zero. By (18) and division by W(logp n), we find that
ES, = 1 + 0(l/n) W(Iog,, n) which is more than we require to complete the proof of the theorem.
4. Beyond expectations. One finds no difficulty in extending Theorem 1 beyond the convergence of expectations to almost sure convergence. The first step is to obtain an understanding of VarS, and this is easily approached though the use of martingales. For the martingale difference sequence defined by di = E(S,,1Fi) E(S,, 1Fi 1) where Fi = a{XI, X2, , X,}, we have the representation
n
S. ES. di,
and, by the orthogonality of the martingale differences, we have
n
VarSn = EIS,, ES,, 12 Ed?.
To help estimate Edi2, we introduce another collection of random variables {Xi, 1 <
i < n} that are assumed to be independent, uniformly distributed, and independent
i
of the random variables {Xi, 1 < i < n}. We then let S,(,) denote the sum of squares
322 JUN GAO AND J. MICHAEL STEELE
of the edges in the spacefilling heuristic tour of {X,, X2,... ?Xi 15ki~Xi+ii... ~Xn}
i
and note by E(S,(,)I.Fi) = E(S,,1Fi 1) that we have
di = E (S. S,',') 1 Fi).
The basic observation is that the tours associated with Sn and SA(') differ by at most six edges. Furthermore, if we recall the oriented distance function d(s, t) defined in §3 and specify integers ji and h by the relations
d(tjl, Tin d(tj, ii) and d(ii, tj~) Tin d(ii, tj),
J:30i
then we obtain the spacefilling tour through {X,, X2,. Xj+1, , X.} by
connecting ~i into the spacefilling tour through {X,, X2.... ~ Xi liXi+17 ... i Xn} by
edges to Xii and Xj, and removing the edge that connects Xj, and Xj, We are thus
led to
5,(i) = S(Xl, X2'. .., Xi
_J, X,+,,..., Xn) + 1 1V,(tjj j112
+ II?p(i
,) _ lp(tj~)112 _ 110(tjj
Similarly, to build the spaceffiling tour through {Xl, X2, Xj from the tour through
{X,, X2, , Xi 1, Xj+1, , XJ, we find ki and k2 such that
d(tk,, ti) = min d(tk, ti) and d(ti, tk,) = min d(ti, tk);
k:koi k:koi
from which we obtain
S. = S(Xl, X2, ..., Xi 1, Xi+j,.. , X.) + 1 ITP(tk~) IP(ti) 112
+ Illp(t,) _ lp(tk~)112 _ illp(tk~) _ 0(tk~)l12_
The implied bound on IS,(0 S, 1 is then
S.1:5 Illp(tjj _ lp(i
j112 + 110(i
,) _ lp(tj,) 112
+ I I?p(tjj) lp(tj.)112 + IJIP(4j p (tj112
+ 1 lp(tk") 112 + 1 llp(tkl) IP(tk~ )112,
_ S'(i) 12 is bou ded by
from which we find by Assumption 4 that E I di 12 < EIS,, n
(19)
(p2 j + p2 (t,' + P2
6c~2,E j + P2(i tj2) + p 2 (tj" tj~) + P2 (tk~, t tk,) (tkl 1 tk2))
The computation of the expectations in (19) are now routine, given the known distribution of the gaps between n (or n 1) points chosen on the unit circle. All of these expectations are 0(l/n2), and hence we have Lemma 9.
LEMMA 9. For n + oo, the variance of the sum of squares of edges S,, satisfies
VarS, = 0(l/n).
Now we are ready to prove the almost sure convergence of S,,.
i
i
1
SQUARED EDGE LENGTHS AND THE TSP 323
THEOREm 2. We have
lim Sn 1 a. s.
n c>o ~0(logp n)
Proof. The remaining steps follow a familiar pattern and will just be sketched. First, we consider a subsequence by letting ni = ri 10g2 il. By Chebyshev's inequality, for any E > 0, we have
00 00
P(1 S.i ES,,i 1 > E) :5 E 2 Y~ VarSni ::~ E 2 E j 1 log 2 i < 00;
i=1 i=2 i=2
so, by the easy part of the Borel Cantelli lemma, for n ce, we have (5', ESni) 0 with probability 1. To stretch the convergence to the full sequence, we look at the largest difference Vi of Sn and S,, as n varies through the intervals (ni, ni+,),
V, max IS. S.~ 1.
""i:Sn:5 i+l
For each n such that ni 1 :~ n < ni, the number of terms that occur in S,, and not in Sni or vice versa is at most 0(ni ni 1) = 0(log 2 j). If A denotes the set of all such terms, then JAI = 0(log 4 i); and, if Li is the largest of these terms, then by Assumption 4 and the classical proof of the fact that the largest gap between n points chosen at random from the circle is sharply concentrated around n 1 log n, we can show that EL? = 0(ni 2 10g2 nj). Since Vi :5 JAILi, we see EVi2 = 0(i 2 log,o i); so, again by the Borel Cantelli lemma, we see that, for n + oo, we have Vi 0 with probability 1, which, in turn, completes the proof of the theorem.
5. Concluding remarks. We have established a striking property of the sum of squares of the heuristic tour provided by the spacefilling curve method. Of the questions that remain open, the most natural are perhaps those that seek a more detailed understanding of W, the periodic function that figures in Theorem 1. The (centered) supremum norm of (p determines the strength of the oscillation of ES,', and almost nothing is known about this norm. Simulations offer little insight because of the slow growth of logpn and the difficulty of estimating ES,'. Still, calculations given in Platzman and Bartholdi [81 would suggest by analogy that the oscillation due to W is not large, perhaps only a few percent. This reinforces the difficulty of obtaining detailed information about (p from simulations.
Another natural question addresses the possibility of obtaining sharp bounds on the tail probabilities P(S.,, > t). In view of the remarkable work of Rhee and Talagrand [9] on the Gaussian tall bound for the optimal, length of the TSP tour length, we axe tempted to suggest that P(S,, : ::~ t) < A exp( Bt2) for all some A and B and all t > 0. Some of the structure that Rhee and Talagrand require (like the martingale used in §4) is available in for S,,, but a detailed understanding of P(S,, ~~ t) seems to require additional insights, since, in particular, S,, may have tails that are much lighter than those of the Gaussian distribution.
Perhaps the most compelling problems suggested by this work concern the behavior of the optimal tours rather than the heuristic cousins. First, if we let S.Tsp denote the sum of the squares of the edges in the (almost surely unique) shortest tour through a random sample of n points chosen from the unit square, do we have
lim, Esi SP = C
n co
324 JUN GAO AND J. MICHAEL STEELE
for some constant C?
Finally, there at least one compelling problem concerning the worst case behavior of the sum of squared edges in an minimal length path. If S is a finite subset of [0, 11 2 and TSP(S) denotes a path of minimal length through the points of S, we suspect that
Mn = Max I jel 12
S:1Sl=n eETSP(S)
is asymptotic to clog n as n oc. By the results cited in the first section, we know Mn = 0(log n) and Mn = Q(log n), but the present methods offer no serious progress toward a full asymptotic result. The periodicity that has been found for ESn shows that subtleties can emerge, though we need not expect them at every turn.
REFERENCES
[1] D. ALDOUS AND J. M. STEELE, Asymptotics for Euelidean minimal spanning trees on random points, Probab. Theory Rel. Fields, 92 (1992), pp. 247 258.
121 J. BEARDWOOD, J. H. HALTON, AND J. M. HAMMERSLEY, The shortest path through many points, Proc. Cambridge Philos. Soc., 55 (1959), pp. 299 327.
[3] M. BERN AND D. EPSTEIN, Worst case bounds for subadditive geometric graphs, Tech. Report, Xerox PARC, Palo Alto, CA, 1992.
[41 J. GAO AND J. M. STEELE, General spacefilling curve heuristics and limit theory for the traveling salesman problem, J. Complexity, 10 (1994), to appear.
[5] D. HILBERT, Ober die stetige Abbildung einer Linie auf ein Fidehenstiick, Math. Ann., 38 (1891), pp. 459 460.
[61 S. C. MILNE, , Peano curves and smoothness offunctions, Adv. Math., 35 (1980), pp. 129 157.
[7] G. PEANO, Sur Une Courbe Qui Remplit Toute Une Aire Plane, Math. Ann., 36 (1890), pp. 157 160.
[8] L. K. PLATZMAN AND J. J. BARTHOLDI, Spaceffiling curves and the planar traveling salesman problem, J. Assoc. Comput. Mach., 36 (1989), pp. 719 737.
[9] W. T. RHEE AND M. TALAGRAND, A sharp deviation inequality for the stochastic: traveling . salesman problem, Ann. Probab., 17 (1989), pp. 1 8.
[10] T. L. SNYDER AND J. M. STEELE, A priori inequalities for the Euclidean traveling salesman problem, in Proc. Sth ACM Sympos. on Computational Geometry, Berlin, 1992, pp. 344349.
i
i i