A Priori Inequalities for the Euclidean

Traveling Salesman

Timothy Law Shyderl

Department of Computer Science

Georgetown University

Washington, DC 20057

J. Michael Steele 2

Department of Statistics

The Wharton School

University of Pennsylvania

Philadelphia, PA 19104

Abstract 1. Introduction

It is proved that there are constants cl, C2, and c3 The purpose of this paper is to provide a priori bound

such that for any set 5 of n points in the unit square

and for any minimumlength tour T of S (1) the sum of on quantities related to the edge lengths of an optimal

squares of the edge lengths of T is bounded by cl log n, travefing salesman (minimumlength) tour through n

(2) the sum of edge lengths of any subset E of T iR points in the unit square. By a priori, we mean that the

bounded by c21EI'I', and (3) the number of edges hav bounds are independent of the locations of the points

ing length t or greater in T is at most c3/t2. The sec Studies of a priori bounds were initiated by Verblun

ond and third bounds are independent of the number sky (1951) and Few (1955). Few showed that for any

of points in S, as well as their locations. Extensions to

set S of n points in the unit square, the length of an op

dimensions d > 2 are also sketched.

The presence of the logarithmic term in (1) is en timal traveling salesman tour of S is at most ,/2n + 1.75.

gaging because such a term is not needed in the case Few's result led to a series of improvements, culminat

of the minimum spanning tree and several analogous ing in KarloAT (1989), where it was shown that Few's

problems, and, furthermore, we know that there always constant could be reduced to less than ,/2. Our results

exists some tour of S (which perhaps does not have

continue in this tradition by giving a priori inequalities

minimal length) for which the sum of squared edges is

bounded independently of n. for three other quantities related to the edge lengths of

an optimal traveling salesman tour.

1 Research supported in part by Georgetown University The interest in and subtlety of our inequalities

1991 Summer Research Award. comes from the fact that, in contrast to the minimum

2 Research supported in part by the following grants: spanning tree (MST) problem, optimal solutions to the

NSF DMS8812868, NSA MDA90489H2034, AFOSR

890301, and DAAL0389G0092. traveling salesman problem (TSP) are not invariant

under monotone transformations of the edge weights.

Permission to copy without fee A or part of this material is granted

provided that the copies are not made or distributed for direct Before giving further details on this connection and

commercial advantage, the ACM copyright notice and the tide of the

other related work, we state our main results. We let

publication and its date appear, and notice is given that copying is by

perirdssion of the Association for Computing Machinery. To copy other jel ix yl denote the Euclidean length of the edge

wise, or to republish, requires a fee andlor specific pemdssion.

8th Annual Computational Geometry, 6/92, Berlin, Germany

@1992 ACM 897915186/92/0006/0344 51.50

344

1

e = {x, y} with vertices x and y in R2 , and, in set Inequalities like (1.1) are important in simulations

tings where the order of the edges of an optimal tour is and investigations in which the square root computa

not important, we represent a traveling salesman tour tions required for Euclidean lengths are deemed to be

by the edge set {el,e2, e,}. In what follows, an too expensive (e.f. the discussion in Steele (1990)). It

itoptimal" traveling salesman tour is a tour that is of was observed in Steele (1990) by an application of the

minimum length when using Euclidean edge weights. spacefilling curve heuristic that one could obtain a re

Our first theorem bounds the sum of squared edge sult like (1.1) for the MST, but without the logarithmic

lengths of any optimal traveling salesman tour. factor. Though this result makes the logarithmic term

Theorem 1. There exists a constant 0 < cl < oo such of (1.1) seem disappointing, the present bound can still

that ifT = {el, e2, , CJ is an optimal traveling sales be of service in many applications where a fully a priori

Man tour of {X,, Z2,_'Xn} C [0,112 and Wn > 2, then inequality would be used.

A further subtlety in (1.1) is that we can easily

n show there always exists some (not necessarily opti

lei J' < cl log n. (1.1) [0,1]2

mal) tour 7' OfS = {Xl,X2,,Xn} C for which

EcIT' lel' < clogn, where c is a constant. This can

Theorem 2 is a bound on the number of edges that be shown by observing via a pigeonhole argument that

are of length t or greater. there exist xi and xi E S, where i 0 j, such that 1 xi xj 1

Theorem 2. There exists a constant 0 < C2 < co such is at most a constant times n 112, then proceeding by

that, ify(n, t) is the number ofei E T such that lei 1 > t, an obvious induction. In fact, it has been known for

then for all t > 0 and n > 1, some time that one can do considerably better; there

is a constant c' and a tour T' of S such that, for all

v(n, t) :5 C2 /t 2. (1.2) n > 2, ZET' JeJ2 < c'. This can be obtained via the

spacefilling heuristic as noted in the discussion of the

Corollary 3 gives a bound on the total length of MST, or it can be obtained by appropriately generaliz

any kedge subset of an optimal TSP tour. ing the Pythagorean Theorem (Neumann (1982)).

Corollary 3. There exists a constant 0 < C3 < oo such The sticky issue for the TSP is that, though there is

that, if E= {ei, , ei,, , ei.} ~; T, then some tour T' that makes le J2 particularly small,

there is no compelling reason to believe that a travel

lei 1 :5 C3"11k. (1.3) ing salesman tour T that Minimizes 1:,.T jel will do

iEE ~ nearly so well. Because of the matroidal properties of

It is interesting to compare these results to their the MST, such issues do not arise in its analysis. Ana

minimum spanning tree analogues. Steele and Sny lyzing the optimal TSP is much more difficult.

der (1989) proved MST analogues to (1.2) and (1.3), At present, we do not know of a way to remove

but these proofs were predicated on a solution to the the logarithmic factor in (1.1), nor do we have a lower

MST problem via a greedy algorithm, hence were not bound that proves the necessity of the logarithmic fac

applicable to the TSP. The best TSP analogue to (1.3) tor. In the final section, we will comment further on

It, for some constant cTsp. this as well as problems concerning points in [0, 1]11 for

was thus vTsp(n, t) :5 CTSPV15

The bounds (1.2) and (1.3), however, are independent dimension d > 2. In Section 2, we prove two technical

of n, the number of points, as well as the locations of results that are applied in Section 3 to prove our main

the points. For this reason, we say that the significantly results.

improved inequalities (1.2) and (1.3) are fully a priori. This extended abstract is an abridged version of

345

the full paper. Some details have been removed and mj, is oriented along the x axis, the midpoint M2 of e2

the original numberings of equations and figures have lies above el, and the midpoint rn3 of e3 lies above e,.

been retained. We can visualize the ei as illustrated in Figure 2, and

note that there are two distinct cases that need to be

2. Edge Lemmas considered.

The second lemma of this section explicates a prop

erty of nonintersecting edges in an optimal TSP tour

and will be useful in the next section, where we prove D3

our main results. Our first lemma gives a simple ge D2

a3

ometrical bound concerning quadrilaterals that assists b3

the proof of the second lemma. In the statement of a2 12 b2

Lemma 1, the term "diagonal" is used to denote a seg a, VA bl

ment connecting nonadjacent vertices of a quadrilat

eral, regardless of whether the quadrilateral is convex. D

Lemma 1. Let L, and L2 be two nonin tersecting line

segments satisfying r < 1Li 1 :5 Or, where P ' > 1. Sup Figure 2. Three nonintersecting lines of a TSP tour

pose the midpoints of L, and L2 are separated by dis and their Di. Here, (x= 1/2.

tance A. If the endpoints of L, and L2 are joined to

form a quadrilateral Q with sides LI, L2, S,, and 52,

then 1Si 1 :5 1 (0 1)r + 3A for i = 1, 2. Moreover, the

2 Since the endpoints of the ei, {a,, a2, a3, bl, b2, b3},

lengths of the diagonals of Q are bounded by Or + A.

are distinct and are on the tour, there is a pair ai, bj

with i 96 j such that ai and bj are joined by a path that

ProoŁ

contains none of the edges el, e2, and e3. The two cases

The 'roof of Lemma 1, which relies on relatively

P depend on whether ji j) = 1 or ji ji = 2, c.f, the

simple geometric observations, is oniitted for the ex more schematic Figures 3a and 3b.

tended abstract. It can be provided on request.

In the case of li ji = 1, we may assume that i = 3

Lemma 2. Let {el, e2,.. ., e.} denote the edges of an

and j = 2, as shown in Figure 3a. We form a new path

optimad traveling salesman tour Of {xl, X2 Xn} c

by deleting e2 and C3 and adding the edges (a2, a3) and

IR2. For each cj satisfying r < iei 1 :5 Or, let Di denote

(b2,b3). By Lemma 1, we can estimate the net change the disk of radius cticil centered at the midpoint of ei,

in the path length as

where a = 1/22 and P = 3/2. If Di, Di, and Di.

are three disks such that no pair of the edges ei, ei,

and ei, has a vertex in common, then, for all r > 0, the

intersection Di, n Di, n Di, is empty. A, 1a2 a31 + ib2 b31 1e21 1e31

2 [!(P 1)r + 6aPr) 2r

Proof. 2

Without loss, we let ij = j for j = 1, 2,1 We (fl 3 + 12afl)r

show that if D1, D2, and D3 have a point in common,

then it is possible to construct a shorter tour through

{xl, X2, , Xn}. We can assume that e 1, with midpoint since 1M2 M31 = A < 2apr, for D2 n D3 0.

346

7

1

For the case of iiji = 2, i = 1 and j = 3, as shown r < leil :5 Pr, and let B be the corresponding set of

in Figure 3b. We now get a shorter tour by deleting even i. We claim the following:

all the ei and adding the edges (b2, b3), (a3, J51), and EtOi(x) + 1: 10i() :S 4,P(x), (3.1)

(al,a2). The net change in weight is iEA iEB

A2 = 1b3 b21 + jb, a3J + 1a2 a, I le, I 1e21 1e31 where 0(.) is the indicator function of the square

<2[ 1 (p 1)r + 6aflrl + Or + 2ai3r 3r 1, 212.

5 To prove the claim, we note that since we have

(2fl + 14afl 4)r, assumed n is even, pairs of edges with index belonging

where IN ~ b21 and 1a2 a, 1 are estimated as before to A do not share an endpoint; the same is true for

and we estimate jb, a31 using the diagonal bound of pairs in B. For 8 = 3/2 and a = 1/22, Lemma 2

Lemma 1 along with the fact that Irni M31 A tells us that no three disks of A intersect and that no

2apr, since D, in D3 three disks of B intersect. Hence, the point x E R2

can belong to at most two disks associated with A and

two disks associated with 8. Furthermore, since any

disk with center in [0, 112 and radius bounded by apr is

contained in [ctflr, 1 + ct,6r12 C [1, 2]2, we need only

concern ourselves'with X E [1,212 . This proves the

Magure 3a. Rebuilding the a2 to h3 palb when claim.

li j 1 . 1 ill Lognina 2. 110 curved arc isa lyalil,

the X'cd edges have been rentovetl,;tivA lite

dashed edges have tx",ldded. If we now integrate (3.1) over z, we obtain a basic

bound on a subset of the squared edge lengths of an

613 optimal TSP tour:

112 leil' < c, (3.2)

aLl

rtgure3h. Rebuilding the tour when li ji 2 where c 36a 2 X1. Finally,

in Letarna 7_ 11e cu~ ares are paths, the X*ed

edgm have been mwvod. and the dashed edges n

have ~ added. < + leil'

The choices# = 3/2 and et = 1/22 are good enough i=1 n112

+ E

k=l PkIn112

where m is the least integer k such that pk n 112 > ~/2.

3. A Priori EdgeLength Bounds It suffices to take rn = P09.120/2n)l , so applying (3.2)

It is now easy to prove our main results. We label the to (3.3) yields the bound

C [0, 112 n

edges of an optimal tour T Of {xl, X2,. .., Xn} le, 12 < c, log n, (3.4)

in order as et, e2, ..., en, and we assume without loss

that n is even. We first construct disks Di of radius where c, is constant as required by Theorem 1.

a ici 1 and center at the midpoint of ei for each 1 < i < n, Returning now to (3.1) and*again integrating, we

where a = 1/22. Let ipi(.) denote the indicator function see that since lei 12: r for all i E A and i E B,

of Dj, i.e., for all X E B2, 0, 1 if X E Di; otherwise

iOi(x) = 0. Let A be the set of alfodd i such that fiAl + JB1) ira 2 r' < 36. (3.5)

347

where 10(.) is the indicator function of the square If we now write v(n, i) as

v(n,t) = l{i : ieil > Q

To prove the claim, we note that since we have

M01 (3.7)

assumed n is even, pairs of edges with index belonging < E 1{ i :'3kt < le,l :5 pk+lt

to A do not share an endpoint; the same is true for k=0

pairs in B. For P = 3/2 and. a = 1/22, Lemma 2 1 }, we can use (3.6) to bound

tells us that no three disks of A intersect and that no where mt minj {,Oj t > vr2

three disks of B intersect. Hence, the point x E R' Y(n, i) as rn l

can belong to at most two disks associated with A and v(n,t) < c E (pk t )2

two disks associated with B. Furthermore, since any k=0

disk with center in [0, 1]2 and radius bounded by a,3r is < C t2 P2k (3.8)

contained in [~ apr, 1 + aflr]2 C [ 1, 212, we need only k=0

concern ourselves with X E [~ 1, 2f. This proves the c t2,

claim. _,82

If we now integrate (3.1) over x, we obtain a basic which is Theorem 2, with C2 = Cp21('82l).

bound on a subset of the squared edge lengths of an Corollary 3 now results from (3.8) by first noting

optimal TSP tour: that n v(n, z) is the number of edges in E of length

IC,12 < C, (3.2) or less, then writing

I:Jejj= 1: leil+ 1: leil

iEE eiEB tiEE

where c= 36a271. Finally, ieii2:t ieil

lei 12 < + lei 12 0 it

(3.3) Integrating the right most term of (3.9) by parts then

< + lei j2, applying (3.8), we obtain

k=l Phin112

where m is the least integer k such that)3'n11' > x/21 ft x d(n v(n, x)) = v/2(n v (n,

It suffices to take m = P093/2( ,/2n)l, so applying (3.2) + t (v(n, t) n) n(t .v/2_) + 12 v(n, z) dx

to (3.3) yields the bound ft

n :5 v(n, x) dx

lei 12 < c, log n, (3.4) t

:5 C2/t.

where c, is constant as required by Theorem 1. (3.10)

Returning now to (3.1) and again integrating, we Inserting (3.10) into (3.9) and setting t = 1E11/2 yields

see that since leil > r for all i E A and i E B, Corollary 3, with C3 = C2.

(JA 1 + IB 1) ira 2 r 2 < 36. (3.5) 5.Concluding Remarks

But, ]AI + IBI 1{i: r < leil :5 pr }J, so This paper investigates features of an optimal TSP tour

that can be explicated without any knowledge of the lo

J{ r < leil :5 fir }1 < cr2. (3.6) cations of the points, and, in some cases, even without

348

knowledge of the number of points. It is surprising that but such an improvement does not seem to be obtain

relatively tight bounds can be obtained under these con able by the present method.

ditions. Two of our main results bring bounds to the We note that the methods of this paper are by no

TSP that have been known for some time for the mini means restricted to the TSP; it is likely that they can

mum spanning tree, but have been elusive for the TSP be used to yield a priori inequalities for other problems,

due to its NPcompleteness. Our results also create a as well.

new open problem: Can the logarithmic term in Theo

rem 1 be removed?

The preceding arguments can be generalized to

d > 2, but, because of uncertainty concerning the loga

rithmic factor of Theorem 1, it seems inappropriate to

give more than a sketch of a generalization to higher di

mensions. The key idea is that in Lemma 2, we showed

that if three of the Di associated with disjoint edges References

had a point in common, then we could find three dis

joint edges cl, e2, and e3 that were close together and

nearly parallel. The existence of these edges then per

mitted us to construct a shorter tour. We used the fact Few, L. (1955). "The shortest path and the longest road

through n points in a region," Mathematika 2,

that the ei did not cross to help provide bounds on the

141144.

cost of modified paths; of course, such arguments are

not available when d > 2. KarlotT, H.J. (1989). "How long can a Euclidean trav

Still, if we consider the possibility that a large num eling salesman tour be?" SIAM J. Disc. Math.

2,9199.

ber N(d) of dspheres Di = D(mi, alei I) C Ed intersect

and that the surface of any sphere in 1Rd can be covered Neumann, D.J. (1982). A Problem Seminar, Springer

with a finite number M(e) of spherical caps with polar Verlag, New York, NY.

angle c, we can again show that we either have a bound Steele, J.M. (1990). "Probabilistic and worstcase anal

like (3.1), with 4 replaced by a constant depending on yses of classical problems of combinatorial opti

d and c, or else we will have three edges that are suffi mization in Euclidean space," Mathematics of

ciently parallel to perndt an argument like that used to Operations Research 15, 749770.

prove Lemma 2. In summary, one can prove Steele, J.M. and Snyder, T.L. (1989). "Worstcase

growth rates of some problems from combina

Theorem 3. There exist positive constants Cd and torial optimization," SIAM J. Computing 18,

Cd such that for any traveling salesman tour T of 278287.

9 Xn} C (0, 11d and for all n > 2, Verblunsky, S. (1951). "On the shortest path through a

le ld 5 Cd log n, (4.1) number of points," Proc. Amer. Math. Soc. 2,

904A 13.

eET

and

> t

vd(t) l{e E T: jel d/td. (4.2)

Just as in dimension two, there is a serious possibility that the logarithmic factor in (4.1) can be removed,

349