Please see PDF version
Operations Research Letters 8 (1989) 237 239 October 1989
North Holland
EFFICACY OF SPACEFILLING HEURISTICS
IN EUCLIDEAN COMBINATORIAL OPTIMIZATION
J. Michael STEELE
Program in Statistics and Operations Research, School of Engineering and Applied Science, Prinecton University, Princeton,
NJ 08544, USA
Received January 1989
Revised February 1989
This note sharpens and generalizes an inequality of Platzman and Bartholdi on the ratio of the cost of the path provided by the spacefilling heuristic to the cost of the optimal path through n points in Rd.
traveling salesman problem * spacefilling curves * Lipschitz mappings * dimension increasing mappings
1. Introduction also measure preserving, i.e. for each measurable
A c [0, Ild, we have
Bartholdi and Platzman [11 recently reviewed XI(O l(A)) = Xd(A),
how one can build heuristics for many problems
of combinatorial optimization in Euclidean space where X, and A2 denote Lebesgue measures in R
by using spacefilling curves that have easily com or R d , respectively.
puted inverses. The purpose of this note is to For a measure preserving Lip. mapping 0 from
examine the efficacy of the spacefilling heuristic. [0, 11 onto [0, 11d to be algorithmically effective,
Specifically, we will sharpen and generalize a one also needs for each X E [0, 11d to be able to
bound of Platzman and Bartholdi [81 on the ratio quickly compute a t E [0, 11 such that
of the length of the tour provided by the spacefill
ing heuristic to the length of the optimal tour.
The spacefilling heuristic for the traveling sales
man problem (TSP) in R d is based on a map 0 A small but sticky point is that by the invariance
from (0, 11 onto 10, 11d that is Lip,, with a = 11d, of domain theorem (Dugundji [31), 0 cannot be
i.e. one to one. Thus, we have to be content with
computing some point in the pre image. Since this
o(s) ~(t) c 1 S t 1 11d note deals with the solution efficacy rather than
the algorithmic efficiency of the spacefilling heur
for a constant c and all 0 < s < t < 1. We should istic, we will not consider the computation of 0 1.
note that it is not possible to have a sudection of For the spacefilling heuristic the most pressing
[0, 11 onto [0, 11d that is in Lipp for 8 > 11d. This issue is to obtain a bound on the ratio of the
follows from the fact that the union of sets length of the tour produced by the spacefilling
0QiIn, (i + 1)Inj), 0 < i < n, must cover [0, 11d, curve to the length of the optimal tour. For the
and for large n [0, l]' is not the union of n balls TSP in R', Platzman and Bartholdi [81 provided a
of radius cn 16 unless P,< 1 Id. bound of order 0(log n), and they conjectured the
In the positive direction, Milne [61 observed existence of a uniform bound independent of n.
that many of the classical spacefillings curves are This conjecture has recently been answered in the
in Lipi/d. Moreover, several of those curves are negative by Bertsimas and Grigni [21 by providing
0167 6377/89/$3.50 0 1989, Elsevier Science Publishers B.V. (North Holland) 231
Volume 8, Number 5 OPERATIONS RESEARCH LETTERS October 1989
an example that shows that in R 2 the ratio can be they appear on the heuristic tour, so we write
as large as c log n for c > 0. S= (X,, X21 xJ, and we assume for each 1 <
The following theorem complements the results i < n there is a ti E=~ [0, 11 such that tl 1< t2 1<
of Platzman and Bartholdi [8] by providing an < t,, with xi = 0(ti). Next, for u > 0 we introduce
explicit upper bound on the efficacy ratio of the two subsets of {1, 2, , n 1} by
spacefilling heuristic in R d for all d > 2. More U(u) = {i: ti,l ti 1 > u, 1 < i < n
over, the proof given here makes clear that one and
does not require any detailed properties of the
spacefilling curve in order to provide ratio bounds. V(u) = (i: o(ti,,) ,p(ti) 1 > U, 1 < i < n
All one needs is that the curve is measure pre The benefit of introducing V(u) is that its cardi
serving and as smooth as feasible. nality g(u) gives a formula for H,,:
m
Theorem 1.1. Let (p be a measure preserving trans Hn g(u) du, (2.2)
formation of [0, 11 onto [0, lld, that is Lipschitz of fo
order a= 11d, i.e. where
Ild m = imax
1 o(x) O(Y) 1 < c 1 X Y 1
for some c and all x, y c [0, 1]. If H,, is the length Thus, we need to find a bound for g(u), and our
of the path through a set of n points S c: [0, 11 d that method for achieving this will depend on first
is constructed using the spacefilling heuristic based obtaining a bound on f(u) = 1 Qu) 1, the cardi
on then for n >, 2 nality of V(u).
(1 + Wd Qu) the intervals [ti, ti + u] do not
H,, ICd log(m/j)} L,, + Wd CdM, (1.2) For i E=
intersect, so if we set
where Ln is the length of the optimal path through Ai=,~([ti, ti+ UD,
{X,, X2, .. 'I X0, m is the length of the longest edge
in the heuristic path, j is the average length of the then, since 4p preserves measure, we have
edges in the optimal path, and wk denotes the
volume of the unit ball in R k or k = d 1 or d. UAU)= L MAj)=Xd U. Ai (2.3)
f i r= U(U) LU( )
Corollary 1.2. We have for all n >, 2 that Now we use Esterman's inequality (2.1) to bound
Hn < (1 + Od_'Cd + ed the right hand side of (2.3). Letting Cn be an
Wd log n)L, (1.3) optimal tour of (Xl, X2, 1 Xn } with length L,
we see by (1.1) and the fact that each xi is
somewhere on the path C, that
11d
2. Proof of main result Ai c T(CU ' Cj, 1 < i < n. (2.4)
We require a preliminary geometric inequality Hence, by (2.2) and EsterTnan's inequality we have
of Esterman [41 that has recently become of inter CUI'd, T
uf(u)=lt( U Ai est in mathematical statistics, cf. Naiman [7], and i C= U(u) )
Johnstone and Siegmund [51. wd 1 c d 1 U (d 1)1dL', + W'C1U.
Lemma 2.1. If T(x, C) C: R d is the set of all points We thus obtain the bound
within distance x of the rectifiable curve C, then for AU) I"d lC d 1 U lldLn + W"Cd. (2.5)
all x >, 0 we have d Xd, Now, to bound g we note that for i E= V(u) in
g (T(x, 0) 1< £0d 1X 'L + Wd (2.1) equality (1.1) implies
where Wd is the volume of the unit ball in R d and L Citi_ti,Iilld>,
is the length of C. >, U,
hence we have
We begin the proof of Theorem 1.1 by assum V(U) c U(c`u'), (2.6)
ing that the points of S are labeled in the order
238
Volume 8, Number 5 OPERATIONS RESEARCH LETTERS October 1989
and thus g(u) < f(c d U d). By (2.5) and (2.6) we Note added in proof
find our basic bound
g(U) 1< Wd lc'ulL, + W'Cd. (2.7) The spacefilling curve heuristic for the TSP
For any 0 < a < m, we can apply the trivial bound goes back at least to unpublished work of S.
g(u) < n 1 for u E [0, a] and apply (2.7) for Kakutani in 1966. The early history of the idea is
U E [a, m]; so, when we integrate in (2.7), we find discussed by R. Adler in the Collected Works of S.
Kakutani, Vol. 11, R.R. Kalman (ed.), Birkhauser,
H, < a(n 1) + Wd IC'Ln log(m/a) Boston, 1986, p. 444.
Wd C" (m a). (2.8)
Finally, since L. < H~ < (n 1) m we have for a
= L.1(n 1) = j that a E [0, m I, so we can let
a = j in (2.7) to find (1.2). To see that (1.3)
follows from (1.2) we use the very crude bound
m < L. and j = Lj(n 1). References
[11 JJ. Bartholdi and L.K. Platzman, "Heuristics based on
3. Concluding remarks spacefilling curves for combinatorial problems in Euelidean
space", Management Sci. M, 291 305 (1988).
The proof of Theorem 1.1 given here uses [21 D. Bertsimas and M. Grigni, "On the spacefiffing curve
heuristic for the Euclidean traveling salesman problem",
several ideas from Bartholdi and Platzman [1], Technical report, Operations Research Center, Massachu
where it was proved that HnIL,, = 0(log n). The setts Institute of Technology, 1989, Oper. Res. Lett. 8 (5),
present approach sharpens and generalizes that (1989) 241 244, this issue.
bound by making systematic use of Esterman's [31 J. Dugundji, Topology, Allyn and Bacon, Boston, MA,
inequality and the bound (2.3). 1970.
[41 T. Esterman, "Cber CaratModorys; and ~owskis
A potentially useful feature of inequality (1.2) Verallgerneinerungen des LAngeribegriffs", Abhandlungen
is the presence of the ratio aus dem Mathematischen Seminar der Hamburgerishen Uni
versiffit 4, 73 116 (1926).
m/i = (n 1)m1Ln. [5] 1. Johnstone and D. Siegnumd, "On Hotelling's formula
The only time the spacefilling heuristic can per for the volume of tubes and Naiman's inequality", Ann. of
form badly is when the longest edge in the heuris Statist. 17,184 194 (1989).
[6] S.C. Milne, "Peano curves and smoothness of functions%
tie path is much larger than the average edge in Advances in Math. 35,129 157 (1980).
the optimal. In the example of Bertsimas and [7] D.Q. Naiman, "Conservative confidence bounds in curvi
Grigni [21, the critical ratio mli is of order n. linear regression% Ann. Statist. 14, 896 906 (1986).
(81 L.K. Platzman and JJ. Bartholdi, "Spacefilling curves and
the planar traveling salesman problem% To appear in J.
Ass. Comput. Mach. (1989).
Acknowledgement
This research has been supported in part by
National Science Foundation Grant #DMS
8812868.
239