Description
As is well-known, there is no polynomial time approximation algorithm for the traveling salesman problem, with bounded ratio, unless P = NP. Consequently, the same holds for the general prize collecting traveling salesman problem. However, one sub-class of the traveling salesman problem for which there is a fixed-bound polynomial time approximation is that where the edge-costs satisfy the triangle inequality.
Ma t h e ma t i c a l Pr o g r a mmi n g 59 (1993) 413- 420 413
No r t h - Ho l l a n d
A note on the prize collecting traveling
sal esman probl em
Dani el Bi enst ock
Department of Industrial Engineering and Research, Columbia University, New York, USA
Mi chel X. Goemans
Department of Mathematics, MIT, Cambridge, MA, USA
Davi d Si mchi -Levi
Department of Industrial Engineering and Operations Research, Columbia University, New York, USA
Davi d Wi l l i amson
Laboratory for Computer Science, MIT, Cambridge, MA, USA
Recei ved Oc t obe r 1990
Revi s ed ma n u s c r i p t r ecei ved 19 No v e mb e r 1991
We s t udy t he ver s i on of t he pr i ze col l ect i ng t r avel i ng s a l e s ma n pr obl e m, wher e t he obj ect i ve is to fi nd
a t our t hat vi si t s a s ubs e t o f ver t i ces s uc h t hat t he l engt h o f t he t our pl us t he s u m of penal t i es as s oci at ed
wi t h ver t i ces not i n t he t our is as s mal l as possi bl e. We pr e s e nt a n a p p r o x i ma t i o n a l gor i t hm wi t h c ons t a nt
bound. The a l gor i t hm is b a s e d on Chr i s t of i des ' a l gor i t hm f or t he t r avel i ng s a l e s ma n pr obl e m as well as
a me t h o d t o r o u n d f r act i onal s ol ut i ons of a l i near p r o g r a mmi n g r el axat i on t o i nt eger s, f easi bl e for t he
or i gi nal pr obl e m.
Key words: Li ne a r p r o g r a mmi n g , pr i ze col l ect i ng, r o u n d i n g f r act i onal s ol ut i ons , t r avel i ng s a l e s ma n
pr obl e m, wor s t - cas e anal ysi s.
1. I nt r o duc t i o n ~
Le t G = ( V, E ) b e a c o mp l e t e u n d i r e c t e d g r a p h wi t h v e r t e x s e t V a n d e d g e s e t E.
As s o c i a t e d wi t h e a c h e d g e e = {i, j } ~ E i s a c o s t ce a n d wi t h e a c h v e r t e x i c V a
n o n n e g a t i v e p e n a l t y ~'i. Th e e d g e c o s t s are a s s u me d t o s a t i s f y t he t r i a ng l e i n e q u a l i t y ,
t hat i s, qi ,j ~
As is well-known, there is no polynomial time approximation algorithm for the traveling salesman problem, with bounded ratio, unless P = NP. Consequently, the same holds for the general prize collecting traveling salesman problem. However, one sub-class of the traveling salesman problem for which there is a fixed-bound polynomial time approximation is that where the edge-costs satisfy the triangle inequality.
Ma t h e ma t i c a l Pr o g r a mmi n g 59 (1993) 413- 420 413
No r t h - Ho l l a n d
A note on the prize collecting traveling
sal esman probl em
Dani el Bi enst ock
Department of Industrial Engineering and Research, Columbia University, New York, USA
Mi chel X. Goemans
Department of Mathematics, MIT, Cambridge, MA, USA
Davi d Si mchi -Levi
Department of Industrial Engineering and Operations Research, Columbia University, New York, USA
Davi d Wi l l i amson
Laboratory for Computer Science, MIT, Cambridge, MA, USA
Recei ved Oc t obe r 1990
Revi s ed ma n u s c r i p t r ecei ved 19 No v e mb e r 1991
We s t udy t he ver s i on of t he pr i ze col l ect i ng t r avel i ng s a l e s ma n pr obl e m, wher e t he obj ect i ve is to fi nd
a t our t hat vi si t s a s ubs e t o f ver t i ces s uc h t hat t he l engt h o f t he t our pl us t he s u m of penal t i es as s oci at ed
wi t h ver t i ces not i n t he t our is as s mal l as possi bl e. We pr e s e nt a n a p p r o x i ma t i o n a l gor i t hm wi t h c ons t a nt
bound. The a l gor i t hm is b a s e d on Chr i s t of i des ' a l gor i t hm f or t he t r avel i ng s a l e s ma n pr obl e m as well as
a me t h o d t o r o u n d f r act i onal s ol ut i ons of a l i near p r o g r a mmi n g r el axat i on t o i nt eger s, f easi bl e for t he
or i gi nal pr obl e m.
Key words: Li ne a r p r o g r a mmi n g , pr i ze col l ect i ng, r o u n d i n g f r act i onal s ol ut i ons , t r avel i ng s a l e s ma n
pr obl e m, wor s t - cas e anal ysi s.
1. I nt r o duc t i o n ~
Le t G = ( V, E ) b e a c o mp l e t e u n d i r e c t e d g r a p h wi t h v e r t e x s e t V a n d e d g e s e t E.
As s o c i a t e d wi t h e a c h e d g e e = {i, j } ~ E i s a c o s t ce a n d wi t h e a c h v e r t e x i c V a
n o n n e g a t i v e p e n a l t y ~'i. Th e e d g e c o s t s are a s s u me d t o s a t i s f y t he t r i a ng l e i n e q u a l i t y ,
t hat i s, qi ,j ~