Please see PDF version
JOURNAL OF COMPLEXITY 10, 230 245 (1994)
General Spacefilling Curve Heuristics and Limit Theory
for the Traveling Salesman Problem
JUN GAO
Program in Statistics and Operations Research, School of Engineering, Princeton
University, Princeton, New Jersey 94305
AND.
J. MICHAEL STEELE*
Department of Statistics, Wharton School, University of Pennsylvania, Philadelphia,
Pennsylvania 19104
Received October 12, 1992
The tour given by the spacefilling curve heuristic applied to a random sample of points from the unit square differs in subtle ways from the shortest tour through those points. In particular, the expected length of the heuristic tour is found to be asymptotic to Vn times a periodic function of log n for a broad class of spacefilling curves. The theory is developed further by detailing the self similarity properties of the spacefilling curve that are useful for obtaining the asymptotics of the expected length of the heuristic path. Finally, the theory of martingales is applied to obtain tail bounds that yield rigorous almost sure asymptotics for the length of the heuristic tours. C 1992 Academic Press, Inc.
1. INTRODUCTION TO THE SPACEFILLING CURVE HEURISTIC
The basic ingredient of the spacefilling curve heuristic is a sudective mapping 0: [0, 11 [0, If such that for each x EE [0, 112 one can quickly compute a t EE [0, 11 such that 0(t) = x. The set of such ip is large, and any of these ip can be used to build heuristic methods for many problems of
Research supported in part by NSF. Grant D1IS92 11634, and ARO Grant DAAL03 91
G 0110. E mail steele@wharton.upenn.eud.
230 0885 064X/94 $6.00 Copyright 0 1992 by Academic Press, Inc. AN rights of reproduction in any form reserved.
SPACEFILLING CURVES AND THE TSP 231
geometric combinatorial optimization. The main purpose of this article is to explore how these heuristics behave. For specificity we focus on the traveling salesman problem (TSP), and mainly we consider geometric features of the tours that one obtains on applying the heuristic to a random samples of points from [0, 111. Still, there is a general theme that is illustrated by these investigations, and it lives in the assertion that many methods of continuous analysis can be of use in problems of discrete optimization. This theme goes at least a little way to suggest that the classical theory of combinatorial computational complexity may not be as distant from the theory of numerical computational complexity as is commonly supposed.
The essential idea of the spacefilling curve heuristic applied to the TSP is the suggestion that we can find a short tour through a set of n points {xl, X2, . . . , Xn} C 10, 112 by visiting the points in the order of their preimages in [0, 1]. More formally, we have a three step process where we (1) compute a set of points {tl, t2, . . . , Q C [0, 11 such that 0(t) = xi for each 1 :5 i n, (2) order the ti so that t(l) :5 t(2) :5 . . . :5 t(,), and, finally, (3) define a permutation or: [1, n] > [1, nj by requiring x,(i) qf(t(i)). The path that Visits {X 1 , X2, . . . ~ Xn} in the order of x,(,), X,(2), . , X,(n) Will be called the spacefilling curve path, and the tour that closes this path by adding the step from Xo.(n) back to x,.(,) will be called the spacefilling curve tour.
For the TSP heuristic built on a spacefilling curve 0 to be effective, one wants tP to be as smooth as possible. Many of the classical spacefilling curves are Lipschitz of order one half, which is to say there exists a constant cp so that for any 0 s, t 1 one has 110(s) 0(01 5 cpl S t1112. Furthermore, one can easily check that no spacefilling curve can be Lipschitz of order greater than one half. To see this, just note that the union of the images of [ilk, (i + 1)1k] for 0:s i < k must cover [0, 112, so at least one of these images must have diameter at least 27r 112k 111.
Many of the classic spacefilling curves have a further property that makes them particularly compatible with probabilistic investigations; they are measure preserving in the sense that for any Borel set A C [0, 112, X1W'(M) = XAM where Xd denotes the Lebesgue measure on Rd. In a later section, we will illustrate how this property helps one to translate many questions about random samples in [0, 112 to simpler questions about a random sample in [0, 11. This stochastic dimension reduction comes unbidden here, but in other contexts it can make light work of problems that otherwise would be perplexing.
As noted in the discussion by Adler (1986), the spacefilling curve heuristic for the TSP dates back at least to unpublished work of S. Kakutani in 1966. Still, the idea has become much better known and better understood since the work of Bartholdi and Platzman (1982, 1988). A particular distinction of these works is that they show that the required preimage
232 GAO AND STEELE
calculation can be done effectively and quickly. The works also illustrate that problems other than just the TSP can be addressed by use of the spacefilling curve heuristic, though on this point one should also note the independent developments of the spacefilling curve heuristic in communication theory by Bailey (1969), in matching theory by Imai (1986), and in real analysis by Kahane (1976) and Milne (1980).
Motivation for the present investigation comes in good part from a
probabilistic result of Platzman and Bartholdi (1989). Suppose Xi, 1 :~ i:~
n, are independent random variables that are uniformly distributed in [0,
I]', and let L SFC = LSFC(Xl, X2_
n . . , Xn) denote the length of a spacefilling heuristic path through {X,, X2, . . . , Xn}. Platzman and Bartholdi (1989) showed that for a specific 0, which had been designed to make the heuristic as effective as possible, there are two constants M' and )3 1 such that
SFC
lim sup ELSFW_n and lim sup EL n Wn ,
n . n .
where j31 8 > 0.
Perhaps the most striking aspect of this result is that it offers a sharp
OPT(Xl, X2, Xn) of
contrast to the behavior of the length L nopT = L n
the shortest path through the random sample {X,, X2, XJ, for
which the famous theorem of Beardwood et al. (1959) tells us that there is
a constant 8 > 0 such that for n > we have
L 0.PTIVn_ , 0,
where the convergence takes place in expectation as well as with probability one.
One goal of this article is to develop the limit resultof Platzman and Bartholdi a bit further with the twin aims of laying out the explicit properties of 0 that are needed to provide an asymptotic understanding of the SF expectation of L n c and of rendering as precisely as possible the nature of
SFC
the oscillatory behavior of Ln Wn_. A second goal of this article is to
SK
complement the understanding of ELn with information on the behavior
SFC _ ELSFCJ _ t).
of the tail probabilities ^Ln n
Bartholdi and Platzman (1989) give few details in their discussion of the SFC almost sure behavior of L n , but part of the plan that they sketch offers to base the almost sure convergence theory of LnsFc on the methods of subadditive Euclidean functionals given in Steele (1981). Since there are substantial differences between the geometry of the spacefilling curve heuristic and that of subadditive Euclidean functionals, this approach does not seem to be an easy one. In contrast, there are major benefits to
SPACEFILLING CURVES AND THE TSP 233
SK be found in basing the almost sure analysis of Ln on martingale difference methods. By applying martingale methods developed for the analysis of optimal TSP tours, one needs little work to produce strong bounds
SK _ EL SK1
on the tail probabilities P(JL, n ~: t). In turn, these make quick
and complete work of the almost sure behavior of L nsFe while contributing
additional understanding of the whole process.
2. STRUCTURAL ASSUMPTIONS AND MAIN RESULTS
For all of the results considered here we assume our spacefilling curves are measure preserving and Lipschitz of order one half; but, to obtain a
SK serious asymptotic understanding ofEL,, one seems to need to bringout further properties of tp. The properties described below are found in many of the classical spacefilling curves, and they reflect the important fact that most of the classical spacefilling curves (such as those of Hilbert (1891) or Peano (1890)) have aspects of self similarity.
AI. Dilation Property. There is an integer p 2 such that for all 0 :S
S, t 1,
110(s) 0(01 ~ltp 0 ( t)
p p
A2. Translation Property. For 1 ~5 i:s p, if (i 1)lp:s s, t:s ilp, then
110(s) 0(01 = 110(s + 1/P) mt + I/01.
A3. Bimeasure Preserving Property. Given any Borel set A in [0, 1], one has
XI(A) = A2WAD,
where Xd is the Lebesgue measure on Rd. The main results of this article are the following two theorems.
THEOREM 1. If a heuristic tour is built using a spacefilling curve 0 that satisfies the Dilation Property (AI), the Translation Property (A2), and the Bimeasure Preserving Property (A3), then there exists a continuous function ~p of period of 1 such that
lim _EL SEc
xl n~o(logp n) where p is the integer appearing in assumptions AI and A2.
1
234 GAO AND STEELE
THEOREM 2. If a spacefilling curve ~p has the Bimeasure Preserving Property (A3), then there are constants A and B such that for all t ~~ 0,
SK ELSFC
P(IELn n 1 ~~ t) ~~ B exp( At2/10g t).
3. PROOF OF THEOREM 1
We first record a simple lemma that makes explicit the correspondence created by tp between uniform random variables in [0, 112 and [0, 11.
LEMMA 1. Suppose X is a random variable that is uniformly distributed in [0, 1]2. Let tp* be a function that for every x EE [0, 112 selects a preimage of x, that is, tp* satisfies tp(qj*(x)) = x. For t defined by t = 0*(X), we have that, if the spacefilling curve satisfies the bimeasure preserving assumption A3, then t is uniformly distributed in [0, 1].
The proof of the lemma can be safely omitted, but one should note that there are measure preserving mappings ip that satisfy AI and A2 while failing to have A3 and failing to have the correspondence property. By the lemma, an independent uniform random sample {X,, X2, . XJ C [0, 112 corresponds under 0* to a uniform random sample {tj, t2, SFC
tn} C [0, 11. Thus, the length L n of the path provided by spacefilling heuristic is given by
n~l
LSFC =
n 110(tw) 0(t(i+l))11,
where t(l),, t(2) :5 :5 t(n) are the order statistics of ti, t2, 4. On
taking the expectation we find
n 1
ELSK fl f' 110(s) ip(t)iifi(s, t) ds dt,
n 00
where fi(s, t) is the joint density of Q(,), t(i+ 1) given by
Ms' t) = n! si 10
(i 1)!(n i 7 M
Here we should remark that this last density formula, as well as those we use subsequently, can be obtained in many ways, through the most general of these seems to be direct integration of the full joint density of (t(l):5 t(2):5 . . . :5 t(n)). If we write the basic simplex as Sn = {(Xl, X2, . . . ' XJ: 0 < xl < . . . < x,, < I}, then the fundamental fact is that (t(l) :5 t(2) 25
'IT
SPACEFILLING CURVES AND THE TSP
235
t(,)) has the density n! I&(x 1 , X2, . . . , x,,), and specialized distributional information about individual variables (or pairs of variables) thus can be obtained by direct integration. For illustrations of the use of the uniform distribution on the simplex to obtain the derivation of expressions like that given forfi(s, t), one can consult Devroye (1986).
The following elementary lemma points out a somewhat surprising formula for the sum of the joint densities of successive order statistics. We
SFC
will use it to write ELn in a simpler form.
LEMMA 2. For 0 :~ s < t 5 1, we have
n 1
fi(s, t) = n(n t + S)n 2.
Proof.
n~l n 12
f
i(S, t) t)
P(t(i) S, t(i+j)
asat
a2 n 1
= 1
asat i=, LI fos
a2 as
at i!(n i)!
= a2 11 (
asat
n!
(i 1)!(n i 1)!
n ! si[(1 S)n i (1 t)n il
ui 1(1 V)n~i 1 du dv
1 Sp (1 t + S)n + (1 t)nl
= n(n 1)(1 t + S)n 2. a
SF
By substituting (1) into the integral representation for ELn c and letting
x = t s, we have
ELSK = 1 X
n fol fo 110(s + x) qj(s)iln(n 1)(1 X)n 2 ds dx.
This is a charming exact formula for the expected length of the heuristic tour, but there is an approximate formula that is a bit simpler and more natural for asymptotic analysis.
LEMMA 3.
EL!FC = n 3/2 fII fll~x
Vn_ 0 0
liqj(s + x) 0(s)iie ds dx + o(l).
236 GAO AND STEELE
Proof. We have to estimate the absolute value A, of the difference between the principal terms
' f' f,' x 110(s + x) tP(s)lin(n 1)(1 x)" '~ ds dx
V n 0 0
and
n3/2 fo' fo' 110(s + X) owile ds dx.
From the completely crude bound 110(s + x) tp(s)~] :5 V2 , we see
1
An :S V2 f. 1n112(n X)n 2 n312e nxidx,
and since 1(1 X)n 2 e nxl :5 f(l X)n (1 Xp 2} + {e nx (1 X)n} easy integrations Show An = 0(n 112), leaving room to spare.
If we define the function k(x) by
k(x) = 1 X tp(s)iids,
fo lio(s + X)
then by the usual considerations of Laplace's asymptotic method, the behavior of EL nsFc/ Vn is determined by the behavior of k(x) in the neighborhood of 0, so we may just as well write
EL Sn FC = n3/2 fq k(x)e dx + o(l),
V n 0
where q = 11p.
We can now generalize an observation from Platzman and Bartholdi (1989) to show there is a function r(x) that captures the scaling properties of 0, and, at the same time, offers an approximation for the function k(x).
LEMMA 4. For q = 1 lp, one can define a continuous function r on [0, with the following properties: (a) r(x) :5 cpVx , 0 :5 x < . (b) ik(x) r(x)i 5 cqx111, 0 :S x q. (c) r(x) = Vpr(xlp), 0 x < ..
Proof. For any 0 :5 x :5 q, we see from the definition of k(x) that
p iq 1
k(x) litp(s) tp(s + x)iids. (1)
SPACEFILLING CURVES AND THE TSP 237
Next, by assumption A2, changing variables, and using assumption AI, we obtain
P q x
x 110(s) 0(s + x)ilds = p liqj(s) O(S + x)ilds
_,)q f,
= fpq p v (s + Px ~l ds
0 p p )
1 = fo, px 110(s) p(s + px)llds
7P
1 k(px). (2)
VP_
By combining (1) and (2), we find the basic fact
k(x) ~: 1 k(px). (3)
VP_
If we replace x by xlp, in inequality (3), we then have k(x) 2s Vp_k(xlp) for 0 :5 x :s 1. Thus, if we define a sequence of functions {f,,(x)},~to by
f ~_ pn 1,
.(X) = pn12k P. 0 < X
(i),
then these functions are pointwise monotonic on ever increasing intervals:
AW :5A+1(x) 0:5 X:5 p (4)
By the Lipschitz property of 0, we have k(u) :5 cp u for 0 :5 u :s 1, so for 0 5 x 5 pn l we have
f
.(X) :5 p(nll)IC,,VXlpol = C'PVX. (5)
The last two inequalities show that for all x 2t 0 that {f,(x)} is a bounded, monotone sequence. We will denote the limit by r(x) and show that this r(x) satisfies the requirements of the lemma. To begin, we see that letting n co in (5) already yields requirement (a).
To obtain the other required properties of r(x), we introduce a sequence of functions g,, that we can show will decrease to r(x). We let
go(X) = C'PX312 + k(x),
238 GAO AND STEELE
and we note by (2) that for 0 :jE~ x :~ q we have
{ P iq x ' iq
go(x) 1 f 110(s) MS + x)llds + P 110(s) qj(s + x)l~ds
i=l U 1)q 71 fi
+ COX3/2
P ' iq
k(px) + f 110(s) 4j(s + x)llds
iq x
+ {CPpX111 Co(p 1)X312}
k(px) + CopX112 + P ' iq
1 R q x 110(s) 0(s + x)llds COXII2
VP_
(6)
By the Lipschitz property of ip, we have
fiq li~(S) O(S + X)11dS COX312 ~_ 0,
iq x
so after replacing x by xlp, we have for 0 x 1 that go(x) ~~: \1p go(xlp). We rescale go to define g,(x) = pn12go(X1pn) and note that our inequality for go yields the monotonicity relation:
9,1W gnll(X), 0 25 X < pn l.
The definition of g, tells us
g f
n(X) ~(X) = CX3121pn, 0 < X :5 pn 1, (7)
SO gn(x) also converges to r(x) as n This implies that for 0 :s x
pn 1,
fn(x) :5 r(x) :5 gn(X). (8)
To show the part (b) we just need n = 0 to see that for 0 :5 x :5 q
k(x) = fo(x) :5 r(x) 5 go(x),
and, consequently,
f
lk(x) r(x)J:51go(x) O(X)I= COX312 0 x q.
SPACEFILLING CURVES AND THE TSP 239
All that is left to finish the proof is to establish (c), but this is almost immediate by the definition of r. We have r (:~) = lin, p,12k ( x
p pl . pn~l
= lim (n + 012k
n_. p
X/P_
r(x)
X/P_
completing the proof of the lemma.
To bring r(x) into action, we note that by the first two parts of the lemma, we have
ELSK n = n3/2 fq r(x)e dx + o(l),
Vn_ 0
= n312 f r(x)e dx + o(l). (9)
Still, the power of this representation is evident only when we use the third part of the lemma to connect r(x) to a periodic function of logp n.
LEMMA 5. There is a continuous function ~o: [0, [0, ) with
period 1 such that
cp(logp n) = nlll.f,' r(x)e dx.
0
Proof. We let I(n) denote the right hand side, divide the interval [0, into subintervals [pkIn, pk+11n], < k < oc, and the make the change of variables x = pk+uln on the subinterval [plIn, pk+11n] to get
An) = n312 pk+11n r(x)e dx
k= PkIn
= V n j 1 r(pk+111n)pk+u eXp(_pk+u) In p du.
k= fo
By Lemma 4, part (c), we have
240 GAO AND STEELE
I(n) = n 1/2 r(plIn)p3k12+ii exp( pk+11 ) In p du
0
= In p r(P ii log,n p (312)(k+u) exp( p`11) du.
fo
We then define the function (p by
(p(x) = In p fo 1 r(p (~' u))1"Y~h(ti) du,
where h is defined by
h(u) p 312(k+ii) exp( pk+u) du.
k=
We note that both h and ~p are continuous, and by the integral representation for I(n) we have
I(n) = ~o(logp n).
Next, to check that ~p is periodic function with period 1, we just note that r(x) = Vp_r(xlp) tells us
~p (x + 1) = In p fo 1 r(p (X+I U))IV 7 (u) du
= In p f,' Vp r(p (x u)lp)IV' ' ~ h(u) du
(p (X) (10)
Finally, we check that (p is bounded from below by a positive constant. To begin we note that by continuity and periodicity there would otherwise be an xo such that ~o(xo) = 0. But by the integral definition of (p this would imply that r vanishes on the interval [p xo, p xo+11, and this in turn would imply that r is identically zero by the recursive property of r in Lemma 4. Hence we conclude that p never vanishes and consequently is bounded below by a positive constant.
Dividing both sides of (9) by ~o(log, n) and applying Lemma 5, we have proved that
EL WC
lim n_ _ = 1.
Vn ~o(logp n)
SPACEFILLING CURVES AND THE TSP 241
4. PROOF OF THEOREM 2
To set up the application of martingale differences, we first let Yk be the
o ficld generated by {Xl, X~,, . . . , XJ, and then define
SKI 5;i)
di = E(Ln E(Ls,Fc~ji ,). (11)
Once can easily check that {di, 1 :s i :5 n}, is a martingale difference sequence and that we have the basic representation
11
LSFC ELSK d.
This type of representation for the optimal tour length L, was introduced in Rhee and Talagrand (1987), and its application was subsequently refined in Rhee and Talagrand (1989b). One can consult these articles for additional information on the role of martingales in problems such as the TSP; and, for general background on the applications of martingales in combinatorics, one does very well by consulting Chap. 7 of Alon et al. (1992).
For the path taken here, we recall two results from Steele (1989). The first is a rather special LP inequality that requires some machinery from martingale theory for its proof, but the second is just an exercise in applying Markov's inequality.
LEMMA 6. Let di, 1 :5 i:5 n, be a martingale difference sequence. If there are two constants cl and C2 such thatfor p > 1 and 1 :5 i :5 n we have
Ildill. :5 cl(n i + 1) 1/2, and
Ildill, :5 CApIn)111 then there is a constant C3 such that
n
:5 C,p112(log p) 112.
LEMMA 7. For any random variable Z, there are constants a and b so that
^IZI ~: t) :s a exp( bt2/log t), t 0,
242 GAO AND STEELE
if and only if, there is a constant c such that for all p ~: 1 that p :E~ CP 1/2(1 og p) 1/2.
The proof of Theorem 2 thus reduces to showing that the martingale differences defined in (11) satisfy the conditions of Lemma 6. To reexpress those conditional expectations in a more convenient form, we introduce independent random variables {Xi: 1 :s i ::~ n} with the uniform distribution on [0, 112 that are also independent of {Xi: 1 :5 i ~5 n}, and we define L SFC(i) = LSFC (X,, X2, . .
n . , Xi 1, ~Ci, Xi,1, Xj. The purpose of introducing these variables is that we find the new representation
SK SK(i)l 9~i).
di = E(Ln Ln
Now we need to find bounds on dj. In sympathy with our earlier notation, we put ii = 0 *(£i), and, for our first crude bound, we use the definition of the heuristic and the Lipschitz property of 0 to find
I SFC SK(i)l
Ln Ln :5 2co min 1 ii tj 1 112 + 2cp rnin 1 ti tj 1 1'2.
i
The reason for the restriction on the j's is brought out when we take expectations and use independence to get the bound
SK SFC(i)i S;i)l SK SF%)11 yi)
Idil = IE(Ln Ln :5 EflLn Ln
:5 2c0E(min Iii tj1112) + 2cpE(min Iti tj 1 1/21 9;i). (12)
i
To complete the computation of these expectations, we note the easy bounds on the tail probabilities
P(min iii tj1112 t) = P(min Iii tjl ~t t2) 5 (1 t2)n i,
i
and
P(min Iti tj11'2 tl 9;j) :5 (1 t2)n i.
i
Since there is a constant a, such that for all m,
f1 (1 t2) dt = 1 7r112F(m + I)/IF(m + 3/2) :5 al(m +
o 2
1
SPACEFILLING CURVES AND THE TSP 243
we see there is a constant a2 such that
E min tj £ P (min tj1112 t) dt ::i~ a2(n i + 1) 1/2
i
and
E(min 1 ti tj 1 1/21 y,,) :5 a2(n +
i
By applying these two bounds in (12) we see that we have established the first condition of the lemma.
Now, we show that there is constant C2 such that
Ildill, CApIn) 1/2.
By the definition of di and Jensen's inequality, we have
SFC SF%) 1 9~i) 1 p SFC SK(i)l p.
Eldi1P = E1E(Ln Ln E1Ln Ln
For p 1 and x ~t 0, y ~~ 0 we have 1x + y JP 2P(xP + yP), so
Eldi1P 2PcpE(min Iti tj1p12) + 2PcOE(min Iti tj1P12).
i2~jsn joi
To bound the last two expectations, we note
1 p
E min Iii tj1P12 tpl2p(min Iii tjl ~~: t) dt
i~tj:sn i2~jsn
:5 P tp/2 10 W1 dt n p12r(p/2)
2 fo 2
c(pIn)P1,
and by a completely parallel argument we also find
E (min 1 ti tj 1 P11) :5 c (p In) P/2;
j94i
so the second inequality in the hypothesis of Lemma 6 is proved. By applying Lemma 7, we conclude the proof of Theorem 2.
Application to Almost Sure Convergence
By Theorem 1 and Theorem 2 together with the traditional BorelCantelli argument, we find the desired strong law:
244 GAO AND STEELE
LsFC
lim 'I = 1 a. s.
X/"n sc(log, n)
One should note that Theorem 2 goes much further than is required for this law; and, in most cases, one does better to use Theorem 2 directly, rather than to call on this corollary. Still, because of the natural connection to the Beardwood Halton Hammersley theorem and the results of Platzman and Bartholdi (1989), the application deserves to be singled out.
5. CONCLUSION
There are two open problems that seem particularly compelling.
1. Is there a spacefilling curve 0 for which the corresponding periodic function ~o is actually a constant? One may have to give up some of the efficacy of the heuristic tours provided by the 0, but one would regain the fundamental behavior of the optimal tours as reflected in the BeardwoodHalton Hammersley theorem. We know from direct computations done in Platzman and Bartholdi (1989) that there are 0 for which (p is nonconstant, but it would be surprising if there were no 0 for which T is constant. After all, as the works of Salem and Zygmund (1945) and many others show, there are methods for constructing bimeasure preserving, Lipschitz one half, spacefilling curves that apparently have little to do with the selfsimilarity properties AI and A2.
2. Can the tail bound of Theorem 2 be improved to provide a bound of the Gaussian form, where no log t factor is required? That is, can one show that for any Lipschitz one half, bimeasure preserving, spacefilling curve that one has constants A and B such that for all t =t 0 one has
PSFC ELSK1
(ILn n ~ t) :5 B exp( At2).
We know from the developments of Rhee and Talagrand (1987, 1989a, and particularly 1989b) that the corresponding Gaussian tail bound does hold for the length of the shortest path. Such an inequality for the spacefilling heuristic paths would seem to be easier than that for the optimal paths, but the problem still does not seem to be easy. Apparently, one cannot easily adapt the method of Rhee and Talagrand (1989b) to obtain a Gaussian tail bound for the length of the spacefilling curve heuristic paths.
REFERENCES
ADLER, R. (1986), Conimentary, in TheCollected Works of S. Kakutani, Vol. IF' (R. R.
Kalman, Ed.), p. 444, Birkhauser, Boston, 1986.
SPACEFILLING CURVES AND THE TSP 245
ALON, N_ SPENCER, J. H., AND ERD6S, P. (1992), "The Probabilistic Method, WileyInterscience Series in Discrete Mathematics and Optimization, New York.
BAILEY, T. (1969), Spacefilling curves: Their generation and their application to bandwidth reduction. IEEE Trans. Inform. Theory 11.15, 658~664.
BARTHOLDI, J. J., AND PLATZMAN, L. K. (1982), An 0(n log n) Planar traveling salesman heuristic based on spacefilling heuristic curves, Oper. Res. Lett., 121 125.
BARTHOLDI, J. L, AND PLATZMAN, L. K. (1988), Heuristics based on spacefilling curves for combinatorial problems in Euclidean space, Management Sci. 34(3), 291 305.
BEARDWOOD, L, HALTON, J. H_ AND HAMMERSLEY, J. M. (1959), The shortest path through many points, Proc. Cambridge Philos. Soc. 55, 299 327.
DEVROYE, L. (1986), Non Uniform Random Variate Generation, pp. 17 19, SpringerVerlag, New York.
HILBERT, D. (1891), Ober die Stetige Abbildung einer Linie auf ein F19chenstack, Math. Ann. 38, 459 460.
IMAI, H. (1986), Worst case analysis for planar matching and tour heuristics with bucketing techniques and spacefilling curves, J. Oper. Res. Soc. Japan 29(1), 43 67.
KAHANE, L P. (1976), Mesure et dimensions, in Turbulence and Navier Stokes Equations" (A. Dold and B. Eckmann, Eds.), Lecture Notes in Mathematics, Vol. 565, Springer Verlag, New York.
MILNE, S. C. (1980), Peano curves and smoothness of functions, Adv. Math. 35, 129 157.
PEANO, G. (1890) Sur une courrbe qui remplit toute une aire plane, Math. Ann. 36, 157 160.
PLATZMAN, L. K., AND BARTHOLDI, J. J. (1989), Spacefilling curves and the planar traveling salesman problem, J. Assoc. Comput. Mach. 36(4), 719 737.
RHEE, R. T., AND TALAGRAND, M. (1987), Martingale inequalities and NP complete problems, Math. Oper. Res. 12, 177 181.
RHEE, R. T., AND TALAGRAND, M. (1989a), Martingale inequalities, interpolation and NPcomplete problems, Math. Oper. Res. 14, 91 96.
RHEE, R. T., AND TALAGRAND, M. (1989b), A sharp deviation for the stochastic traveling salesman problem, Ann. Probab. 17, 1 8.
SALEM, R., AND ZYGMUND, A. (1945), Lacunary power series and Peano curves, Duke Math. J. 12, 569 578.
STEELE, J. M. (1981), Subadditive Euclidean functionals and non linear growth in geometric probability, Ann. Probab. 9, 365 376.
STEELE, J. M. (1989), Seedlings in the theory of shortest paths, in Disorder in Physical Systems: A Volume in Honor of J. M. Harnmersley" (G. Grimmett and D. Welsh, Eds.), Cambridge Univ. Press, Cambridge, MA. ,