Operations Research Letters 8 (1989) 237239 October 1989

NorthHolland

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(Ol(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. onetoone. Thus, we have to be content with

computing some point in the preimage. 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 01.

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

01676377/89/$3.50 0 1989, Elsevier Science Publishers B.V. (NorthHolland) 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

Johnstone and Siegmund [51. wd 1 c d1 U (d1)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"dlC d1 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< Wdlc'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) + WdIC'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, 291305 (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) 241244, 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, 73116 (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,184194 (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,129157 (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, 896906 (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