Please see PDF version
MATHEMATICS OF OPERATIONS RESEARCH Vol. 11, No. 2. May 1986 Printed in U. S.A.
PROBABILISTIC ALGORITHM FOR THE DIRECTED
TRAVELING SALESMAN PROBLEM*t
J. MICHAEL STEELE
Princeron University
A model is given for a random directed traveling salesman problem (DTSP). The asymptotic behavior of the optimal solution of the DTSP is determined, and this result is used to establish an t optimal probabilistic algorithm for solving the DTSP in polynomial time.
1. Introduction. In Karp (1977) the problem is posed of formulating a probabilistic model of the directed traveling salesman problem (DTSP) for which one can establish a probabilistic polynomial time algorithm. The main objective of this article is to introduce one such model.
In fact, the model studied here is about the most obvious model one could imagine for the DTSP. The hard part is to obtain enough probabilistic information from the model to be able to show the existence of a good algorithm.
To specify the model we first suppose that Xi, 1 < i < oc, are independent random variables with the uniform distribution in the unit square [0, 11 2 . As the vertex set of a directed graph G, in R 2 we take V. = {X 11 X21 .... Xn). Now, we suppose that for 1 ~ i It may not be apparent that there is always a directed path through V, This follows from a classic result o~,gidei (1934) and will be established algorithmically in the next section.
The main result on Dn which will be proved here is the following:
THEOREM 1. There is a constant 0 < fl < oo such that as n > oo
ED, ~#Fn . (1. 1)
The main consequence of this asymptotic relationship is the existence of a probabilistically efficient algorithm for the DTSP.
THEOREM 2. There is a polynomial time algorithm which provides a directed path through V, which has length D* satisfying
EDn .~ (1 + c)EDn, (1.2)
for all c > 0 and n > N(t).
The sense of optimality in this result is a bit weaker than that obtained by Karp (1976), (1977), and the reasons for this difference are discussed in the final section.
*Received November 2, 1981; revised March 21, 1985. A MS 1980 subject classification. Primary: 60D05. Secondary: 90C42. IA OR 1973 subject classification. Main: Graphs. OR/ MS Index 1978 subject classification. Primary: 490 Networks/graphs/traveling salesman. Key words. Directed travelling salesman problem, probabilistic algorithm, Euclidean functionals. tThis research was supported in part by Office of Naval Research Grant NOOD14 76 C 0475 and NSF Grants DMS 8414068, and DMS 8414069.
343
0364 765X/86/1102/0343501.25
Copyright C 1986. The Institute of Management Sciences/Operations Research Societ> of America
344
11~
J. MICHAEL STEELE
The proof of Theorem 1 is given in the next three sections. In the first of these, a procedure is given for sewing together the subproblems of a natural decomposition of the DTSP. The inequalities provided by this procedure are used in §3 to obtain the asymptotic behavior of the Borel average of the ED, Finally, the Tauberian theorem of R. Schmidt (1925) is used in §4 to complete the proof of Theorem 1.
In §5 the sewing method and Theorem 1 are used to complete the proof of Theorem 2. The last section compares results obtained here for the DTP with Karp's original work on the TSP and isolates a basic open problem.
TECHNICAL REMARKS. (1) By a directed path we mean a sequence of directed edges e,, e2, . . . , e, such that if e, = (xi, y) then x,, 1 = y, for each 1 < i < n. In particular it is possible for a vertex x to appear more than once on the shortest path. This is a complication that cannot arise in the undirected TSP.
(2) The fact that P > 0 is a consequence of the fact that the length of the DTSP is at least as large as the corresponding TSP. Thus, P > 0 follows from Beardwood, Halton, and Hammersley (1958). To see this even more easily one can note that the expected distance from any point in {X,, X2, . . . , X,,} to its nearest neighbor is bounded below
1/2
by en
2. Sewing inequalities. As promised, we will first establish R~dei's theorem that any complete digraph G has a directed path through all its vertices. Suppose a partial
path xj,,xj X 'k ~ 1 ~ k < n, has been constructed through part of the vertex set
{X 11 X21 xn). We can choose x. arbitrarily from the remaining vertices and show
7
that it can be included in an augmented path. If (x., x,.) E= E then x. > xi > > x,,
E by the completeness of'G. Now, if
is such a path, and otherwise (xi, xj) E=
(xj, xi) EE E we see xi, > x, > xi, > . . > x,, is a path, while if (xj, xi) e E we proceed
to x,,. Either we eventually succeed in inserting xj somewhere inside the path or else we
have shown that xi, > Xj2 X. > X. is a legitimate path. This procedure is basic
3k ) '. ~
to the inequalities proved here and will be used repeatedly in the sequel.
Now for some probabilistic considerations. Instead of directly studying Xi, 1 <. i < oo, i.i.d. UfO, lf, it will be convenient to consider a Poisson process II in R' with constant intensity 1. For each Borel A C R' we note that II(A) is a finite point set with cardinality NA = III(A)l where NA is a Poisson random variable with mean X(A), the Lebosgue measure of A. We let R2 be ordered by Lexico graphical order (<<), and for each pair of points x << y we define a Bernoulli random variable Y.,Y. We require (1) ^ Yy 1) 1/2 ^ Y.~y = 0), (2) the collection Y = { Y,,y : x 4, y, x, y E W} an independent collection, and (3) the collection Y is independent of Il.
A new process D(t) is defined as the length of the shortest path through the points of rjfo, 112 using only those edges (x. y) for which xc y and Y.,, = 1, or y ~C x and Y,y 0. By E(t) we will denote the set of such legitimate directed edges between the points of 11[0,tf.
The point of introducing D(t) is the fact that it is a sort of smoothed version of D, This is made explicit, and useful, by the key identity
ED(t) t(EDn)e A12. IM.
n 2
(2.1)
To see why (2. 1) holds we note that conditionally on the event {III([0, tl')1 = n}, the random variables D(t) and tD,, have the same distribution. Since lrl([0, t12)l is Poisson with mean t2, (2.1) just expresses the identity ED(t) = E(E(D(t))l Iii(fo, t]2)1).
We now let .0(t) = ED(t) and proceed to prove the first of the sewing inequalities which are needed to obtain the asymptotics of 0(t).
LEMMA 2. 1. There is a constant c > 0 such that
sb(2t) < 40(t) + ct, 0 < t < oc.
1
(2.2)
DIRECTED TRAVELING SALESMAN PROBLEM: PROBABILISTIC ALGORITHM 345
PROOF. Let Qi, 1 ~~ i < 4 denote the four quadrants of the square [0, 2 t12 , and
suppose that XC >X2 > . . . )~x,, and are the optimal directed
paths through the sets rI( Q) and M Q2) respectively. Next, we let
,r= {mink :(x,,x')EE(21), 1 < k < v)
and let r = oc if (x.,x') e E(2t) for all 1 < k < v or if R1WA = 0. Similarly, we let k
.r'= min(k : (x,,,xk) EE E(2t), 1 %~ k < u}
and T = 00 if (X, Xk) (1 E(2t) for all 1 < k < u or if Irl( Q1)i 0.
v
Now if r < cc and 7' < oo we see that
X. > X,' > X,' ' 1 > > X,', > X,,, ) X,, + 1 X. 1 > X. (2.3)
is a circuit C,2 which goes through all the points of W Q1) U M Q2) except for at most the set Z12 = {Xk', 1 < k < rj U {xk, 1 < k < T'). (See Figure 1(a).) In a similar fashion we construct a circuit C34 through all the points of 1 1( Q3)u n( Q4) except for a set Z34. For the last step in our construction we pick x EE C121 y E E C34 and apply R~dei's algorithm to obtain a directed path P through (X, Y} U Z12 U Z34 which visits each point at most once. Finally, we describe a (suboptimal) directed path through U[0, 2 1f. Without loss of generality we may suppose x comes before y on P. For our suboptimal path we take P until we get to x then we take the circuit C12 back around to x, then we take P until y, make the circuit C34 back toy, and finally finish off the path P. (See Figure 1 (b).)
We now need to estimate the expected length of this suboptimal path through 11[0, 2 t]2. First we bound L (P), the length of the path P, by noting that no edge of P is longer than t2F2 ; and there are exactly 2 + IZ121 + IZ341 vertices on P. This provides the bound,
EL(P) <, t2F2 (1 + EIZI21 + EIZ341) < 16t (2.4)
where we have used the fact that IZ,21 is majorized by a geometric random variable with parameter p = 1/2 so E 1 Z 121 = E 1 Z341 = 2.
For the length of C12, L(CU), we note
U ] V ]
L(C12) < Xi Xi+ 1 1 + xi Xil+ 11 + lx. X111 + lx., XA. (2.5)
Since lx. x,'I and ix' x,.1 are less than tF3, taking expectations in (2.5) gives
EL(C12) < 2.p(t) + t2F3 (2.6)
d Naturally we obtain the same inequality for C34 since L(C34) = L(C12).
From (2.4), (2.6), and the fact that the path we have constructed is suboptimal we
b)
xl X2 % %
XX
r. 3
r'c 2
C34 Y
x'v X~ X~ X,(
FiGuRE 1. Illustration of Lernma 2.1.
346
have 1, bound
J. MICHAEL STEELE
0(21) < EL(C12) + EL(C34) + EL(P)
,< 40(t) + 30f. a
LEMMA 2.2. There is a constant c > 0 such that
0(3t) ~, 90(t) + ct, 0 < t < oc.
1
1~
(2.7)
(2.8)
PROOF. The proof is essentially that used before except that the fact that 9 is odd forces some asymmetry. a
Before applying these lemmas to the asymptotics of 0(t), it is worth summarizing a consequence of the sewing procedure which will be useful in the algorithm of §5. We state this as a lemma.
LEMMA 2.3. Suppose that d,,, is a complete digraph with arbitrary vertex set (x,, X2, . ..,X.) C [O,S12 and with the directions of the edge set determined by independent Bernoulli random variables. Let Q, 1 < i ~ 4, denote the four quadrants of 10, sf and let Di denote optimal (or suboptimal) D TSP tours for the restricted digraph d, with vertex set Qi n {x,,x,,. .., x.). If D is the solution of the DTSP for G we have
ED < ED, + ED2 + ED3 + ED4 + CS.
(2.9)
PROOF. This lemma just spells out the consequences of the procedure of Lemma
2.1 in the case of a slightly different model. In particular one should note that in
Lemma 2.1 no use was made of the distribution of the points of rI[O, 112. c
3. A"ptoties from Inequalities.
LEMMA 3. 1. Suppose that [0, oc 1 > (0, oo) is any continuous function which satisfies
~(2t) < 40(t) + ct and fflt) ,~ 90Qt) + ct, 0 ~~ t ~Q oo.
One then has
lim ~(t)1t2= liminf~ (t)/12= p < 00.
t~co t ~00
PROOF, Forj = 1, k = 1, it is trivial from (3.1) and (3.2) that
0(2) . t) Q 22jy,(t) + ct 2: 2' and
j 1.Q sQ 2(j 1)
fflkt) ~Q 32k~(t) + ct 1: 33.
k 1 <.v < 2(k 1)
(3.1)
(3.2)
(3.3)
(3.4)
(3.5)
These more general inequalities (3.4) and (3.5) are easily verified by induction. Using both of these we see
~(2j3 kt) <. 22i~(3 kt) + ct3 k 2 r
j~ 14 2(j 1)
,Q 2'j { 3'k~(t) + ct
< (2j3 k)20(t) + (V3 k)2Ct.
33 + c& 2: 2'
} J 14sC2(j 1)
(3.6)
Now consider (n, < % < {2j3 k:j> 0, k > 0) = S. For any e > 0 there exist
i
DIRECTED TRAVELING SALESMAN PROBLEM: PROBABILISTIC ALGORITHM 347
posi tive in tegers a, b, c, d wi th 1 < 2` 3 1 + E and 1 < Y2 d , 1 + c. For n, sufficiently large we must have n, divisible by either 3' or 2 d and hence either 2a3 bn, E: S or Y2 dn, c S. In either case we see n', , 1 4Q (1 + e)n so we have p~, , 1 / n', = 1.
Now fix E > 0 and let 0 any real number such that there is an interval (t., i ) for which
~p(t)/12 + C1t2 Q p + E, to Q 11 (3.7)
By (3.6) we see 0(u)lu 2 < 8 +,E for all n E E U 2JY(to, t 1) U n., (to ~ 11),
j,k S
But n, t 1 > n., , 1 to for all s such that n, + 1 In., < 11 / to, i.e., for all s sufficiently large.
By taking p = MaXI"~",~,{1p(t)/t2 + Cltl} we see that litn SUP 0(1)/ t2 ~ .8 < 00 . Then by taking P = liminfo(t)/t2 We See liMSUp~p(t)/t2 < liminf~(t)/I2. 5
When we apply the preceding lemma to the function 0(t) we obtain after some simplification the basic asymptotic relation for the Borel transform of ED,
n
c ~ I ED,, PFX as A > oc. (3.8)
n 2
4. Tauberian step.
LEMMA 4.1. The relation
lim e a,,= c (4.1)
A ~, 00 n!
implies a,, > c if and only if
lim lim inf min {a,,, a.) > 0. (4.2)
ffiy()+ n, ~m
REMARKS. This is the Tauberian theorem for Bore] summability due to R. Schmidt (1925). For a discussion in a modern probabilistic context and many related references one may consult Bingham (1981).
The preceding lemma does not apply directly to the asymptotic behavior of ED, but we will shortly show that the choice a,, n 112ED. will complete the proof of Theorem 1.
LEMMA 4.2. (a) ED, ,Q ED, + 2F2,
xl: 00 2(X "/ n!)(ED.,)l Fn = c, 0 < c < oc.
(b) limx.. e n_
PROOF. The first inequality follows from Ridei's algorithm since the passage from D,, to D,,+ I adds at most two edges which are each bounded by F2 . One consequence of this inequality is the crude bound
ED,, < 5 n. (4.3)
Now setting
(ED,,)1Fn
h(X) e ;k E j!
n 2 we see
X' X ED, (4.4)
h (X) < e (5Fn + e~xs
n o n 2
i
i
348 J. MICHAEL STEELE
so letting s = [(1 E)X] we see from (4.4) and (3.8)
lim sup h (X) 1 E) 1/2e, for all c > 0. (4.5)
X~oo
The lower bound is just as easy since for S = [(1 + E)X],
h(A) > e xs 1/2 Xn EDn> e "s 1/2 5F,
E n! n s+1 nf
n=2 (00)
From (3.8) and (4.6) we have
lim inf h (X) > ( 1 + E) 112C, (4.7)
and the inequalities (4.5) and (4.7) naturally complete the proof of the lemma. a
LEMMA 4.3. For an n '12EA, we have
lim lim inf min (an, an} > 0. (4.8)
>o+ n ~ cc n~m,~n+t~n
PROOF. We have to bound
min {am an} max {m'12EDn n'12EDn
n < mQ n+cFn n.Qm
To do so we note xy xy'= (x x')y + x'(y y'), so for n < m < n + EFn
m n
m _'12ED < n '12EDn + E ((n + k)~ 1/2 ED,, (n ~"k 1) 1/2 EDn + 1
k 1
m n
< n 112EDn + E (n + k1) 1/2 E(Dn+k Dn+k 1)
k 1
< n t 12EDn + E2F2 (4.9)
One then sees that for all n,
min {am a,,} > E2F2 (4.10)
n.Q m < n + t~n
so (4.8) follows immediately. a
With the assumption of the last two lemmas we are able to conclude that EDn~#Fn as n > oo and thus complete the proof of Theorem 1.
5. An efficient algorithm. The algorithm given here is based on geometric partitioning and dynamic programming. We first recall that the m city TSP can be solved by a dynamic programming in time 0(m2) (Beliman 1960, Held and Karp 1972). Almost without modification the dynamic programming algorithm can be used on the DTSP and the same time bound holds.
Now we spell out the DTSP analogue to Algorithm A of Karp (1977). First we choose a real sequence t(n) satisfying
1091092n < t(n) < 41091092n, (5.1)
(n / t (n)) 1/2 = 2j for some j = 0, 1, . . . (5.2)
We also need some notation for a decomposition of the unit square Q = [0, If. We let Qi, 1 < i < 4, denote its four quadrants, and for each i we let Qjj, 1 < . j < 4 denote
DIRECTED TRAVELING SALESMAN PROBLEM: PROBABILISTIC ALGORITHM 349
the four quadrants of Qi. More generally, for each s we let Qi,j, ~ ~', 1 ,~ i" < 4, denote the four quadrants of Qi,j,_. i,_,. We can now sketch the procedure.
DTSP Algorithm. (1) Decompose [0,112 into 4 k subsquares for k
log2(n / t (n)).
2
(2) Use dynamic programming to find an optimal solution for the DTSP in each subsquare Qi.j,... i,.
(3) For s k until 1 and for all 1 ,Q i. 4Q r, 1 < j lQ s, sew the paths obtained in
J
C.'2 4 together by the method of §3 in order to get a path through
Q"2. 1 *
It is easy to see that this algorithm runs in expected time 0(n logn). It remains to check that under the model of the random DTSP studied here that the algorithm provides a nearly optimal solution,
If we let Oi,i,... i,, denote the length of the optimal path through the vertices of Qi,'2. ' "A then inequality (2.9) says that these can be sewed together to get a path through the vertices of Q,'2 k , of length Li,j,._ i,,_, satisfying
L c2 '.
1 < i,,,z 4
If Li,j_. ' is the length of the path through the vertices of Qi,j,... i~, 1 ~~ s ~Q k, obtained by our algorithm then using inequality (2.9) starting from (5.3) we find for s = k j
j
Li,'2' 4 11 0i,i2 ik + c >; 2~`J`. 4` (5.4)
14 i,<4
k j+ ],Q IQ k If we let D,*, denote the length of the path given by the algorithm, then settingj k in
(5.4) and simplifying will give k
Oi,i2 i,+ c2 . (5.5)
1 I.r.j
Now since Qi,j,... j, has area p = 4 k = t(n)ln the number of vertices in Qi,j. ... , is distributed as a binomial random variable with parameters n and p we see by conditioning that
(n),,j(, _ P)n jE(D
j j). 2 k. (5.6)
j 0
From (5.5) we get
~n l (n)pj(l
t (n) P)n jE(D
ED, , < 1 j j) + C~nlt(n) (5.7)
j 0
Since pn = t(n) and since EDk~.8Fk the binomial sum in (5.7) is asymptotic to
#~t(n) . From this we see the whole right side of (5.7) is asymptotic to #Cn. This bound completes the proof of Theorem 2.
6. Open problem. The results of this article are pointed toward the establishment of algorithms which perform well in terms of the expected length of the solution obtained. This is somewhat in contrast to the original conception of Karp (1977) where a similar algorithm is shown to provide an £ optimal solution with probability one (see
350 J. MICHAEL STEELE
also Steele 1981b and Weide 1978 for some subsequent refinements and elaboration of Karp's theory.)
It is natural to ask if the present model will also yield an c optimal algorithm with
probability one. The basic step would consist in proving the natural conjecture
D,, p~ n, with probability one. (6.1)
There are three approaches which have succeeded in similar problems (Beardwood, Halton and Hammersley 1959 and Steele 1981a,c, but these methods do not seem capable of proving (5.1).
References
fl] Beardwood, L, Halton, J. H. and Hammersley, J. M. (1959). The Shortest Path Through Many Points. Proc. Cambridge Philos. Soc. 55 299 327.
121 Bingham, N. H. (198 1). Tauberian Theorems and the Central Limit Theorem. Ann. Probab. 9 221 23 1.
(31 Karp, R. M~ (1976), The Probabilistic Analysis of,Some Combinatorial Search Algorithms. Algorithms and Complexity: New Directions and Recent Results. J. F. Taub (Ed.), Academic Press, New York, 1 19.
[4) (1977). Probabilistic Analysis of Algorithms for the Traveling Sa)esman Problem in the Plane. Math. Oper. Res. 2 209 224.
[5] R~dei, L. (1 934)~ Ein Kornbinatorischer Satz. A eta Szeged 7 39 43.
[61 Schmidt, R. (1925). Ober das Borelsche Summierungsverfahren. Schriften K~nigsberger get. Geselischaft 1205 256.
171 Steele, J. M. (1981a). Subadditive Euclidean Functionals and Non Linear Growth in Geometric Probability. Ann. Probab. 9 365 376.
(81 (1981b). Complete Convergence of Short Paths and Karp's Algorithm for the TSP. Math. Oper. Res. 6 374 378.
[91 (1982). Optimal Triangulation of Random Samples in the Plabc, Ann. Probab. 10 548 553.
110) Weide, B, W. (1978). Statistical Methods in Algorithm Design and Analysis. Thesis, Department of Computer Science, Carnegic Mellon University.
DEPARTMENT OF STATISTICS, PRINCETQI~ UNIVERSITY, PRINCETON, NEW JERSEY 08544
1
1