Please see PDF version
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 minimum length 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 (minimum length) 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 ,/2 n + 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 DMS88 12868, NSA MDA904 89 H 2034, AFOSR
89 0301, and DAAL03 89 G 0092. 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 pem dssion.
8th Annual Computational Geometry, 6/92, Berlin, Germany
@1992 ACM 89791 518 6/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 k edge 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 non intersecting 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 non adjacent vertices of a quadrilat
eral, regardless of whether the quadrilateral is convex. D
Lemma 1. Let L, and L2 be two non in tersecting line
segments satisfying r < 1Li 1 :5 Or, where P ' > 1. Sup Figure 2. Three non intersecting 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 on iitted 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 ii ji = 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 X 1. 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 n 112to guarantee that AI < 0 and A2 < 0. m 1 12,
+ E
k=l Pk In 112
where m is the least integer k such that pk n 112 > ~/2 .
3. A Priori Edge Length 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
M0 1 (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 t 2 P 2k (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 t 2,
claim. _,8 2
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= 36a 27 1. Finally, ieii2:t ieil n E2 + x d(n v(n, x)).
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 Ph in 112
where m is the least integer k such that)3'n 11' > x/21 ft x d(n v(n, x)) = v/2 (n v (n,
It suffices to take m = P093/2( ,/2 n)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 = 1E1 1/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 < cr 2. (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 NP completeness. 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
141 144.
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,91 99.
ber N(d) of d spheres 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 worst case 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 pern dt an argument like that used to Operations Research 15, 749 770.
prove Lemma 2. In summary, one can prove Steele, J.M. and Snyder, T.L. (1989). "Worst case
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 278 287.
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