3/ 2 - Approximation Algorithm for a Generalized, Multiple
Depot, Hamiltonian Path Problem
Sivakumar Rathinam and Raja Sengupta
RESEARCH REPORT
UCB- ITS- RR- 2007- 2
October 2007
ISSN 0192 4095
1
3 2
¡ A p p r o x i m a t i o n A l g o r i t h m f o r a G e n e r a l i z e d ,
M u l t i p l e D e p o t H a m i l t o n i a n P a t h P r o b l e m
S i v a k u m a r R a t h i n a m 1 a n d R a j a S e n g u p t a 2
A b s t r a c t
W e c o n s i d e r a G e n e r a l i z e d , M u l t i p l e D e p o t H a m i l t o n i a n P a t h P r o b l e m ( G M D H P P ) a n d s h o w t h a t i t h a s a n a l g o -
r i t h m w i t h a n a p p r o x i m a t i o n r a t i o o f 3
2 i f t h e c o s t s a r e s y m m e t r i c a n d s a t i s f y t h e t r i a n g l e i n e q u a l i t y . T h i s i m p r o v e s o n
t h e 2 - a p p r o x i m a t i o n a l g o r i t h m a l r e a d y a v a i l a b l e f o r t h e s a m e .
K e y w o r d s
A p p r o x i m a t i o n a l g o r i t h m s , H a m i l t o n i a n p a t h p r o b l e m , T r a v e l i n g s a l e s m a n p r o b l e m , V e h i c l e r o u t i n g .
I . I n t r o d u c t i o n
R e c e n t l y , w e [ 2 0 ] p r e s e n t e d a 5
3 ¡ a p p r o x i m a t i o n a l g o r i t h m 1 f o r o n e v a r i a n t o f t h e m u l t i p l e d e p o t
H a m i l t o n i a n P a t h P r o b l e m ( H P P ) . A p a r t f r o m t h i s r e s u l t , t h e r e a r e n o a l g o r i t h m s i n t h e l i t e r a t u r e
w i t h a p p r o x i m a t i o n r a t i o s b e t t e r t h a n 2 f o r a n y v a r i a n t o f t h e m u l t i p l e d e p o t T r a v e l i n g S a l e s m a n
P r o b l e m ( T S P ) o r m u l t i p l e d e p o t H P P . T h i s p a p e r c o n s i d e r s a d i ® e r e n t , g e n e r a l i z e d v a r i a n t o f t h e
m u l t i p l e d e p o t H P P a n d s h o w s t h a t i t h a s a 3
2 - a p p r o x i m a t i o n a l g o r i t h m . S p e c i ¯ c a l l y , t h i s p a p e r
a d d r e s s e s t h e f o l l o w i n g G e n e r a l i z e d M u l t i p l e D e p o t H a m i l t o n i a n P a t h P r o b l e m ( G M D H P P ) : G i v e n a
s e t o f k d i s t i n c t d e p o t s w h e r e a s a l e s m a n i s p r e s e n t a t e a c h d e p o t , a p o s i t i v e c o n s t a n t p a n d a s e t o f
n d e s t i n a t i o n s t o v i s i t , t h e o b j e c t i v e o f G M D H P P i s t o
² c h o o s e a t m o s t p s a l e s m e n ,
² a s s i g n p a t h s t o t h e c h o s e n s a l e s m e n s u c h t h a t e a c h d e s t i n a t i o n i s v i s i t e d e x a c t l y o n c e b y o n e c h o s e n
s a l e s m a n , a n d ,
² t h e s u m o f t h e c o s t o f t h e p a t h s o f a l l t h e c h o s e n s a l e s m e n i s m i n i m i z e d . T h e c o s t o f a p a t h i s t h e
t o t a l c o s t o f t h e e d g e s p r e s e n t i n t h e p a t h .
G M D H P P i s a g e n e r a l i z a t i o n o f a s i n g l e d e p o t , s i n g l e s a l e s m a n H P P c o n s i d e r e d b y H o o g e v e e n [ 1 2 ]
a n d i s N P - H a r d . I n [ 1 2 ] , H o o g e v e e n p r e s e n t e d a 3
2 ¡ a p p r o x i m a t i o n a l g o r i t h m f o r a s i n g l e d e p o t , s i n g l e
s a l e s m a n v e r s i o n o f t h e G M D H P P . I n g e n e r a l , t h e r e a r e t w o s u b p r o b l e m s w h e n d e a l i n g w i t h a n y
m u l t i p l e d e p o t r o u t i n g p r o b l e m . T h e ¯ r s t s u b p r o b l e m i s t h e p a r t i t i o n i n g p r o b l e m w h i c h e s s e n t i a l l y
r e q u i r e s ¯ n d i n g a s u b s e t o f d e s t i n a t i o n s f o r e a c h s a l e s m a n t o v i s i t . G i v e n t h e s u b s e t o f v e r t i c e s f o r a
s a l e s m a n t o v i s i t , t h e o b j e c t i v e o f t h e s e c o n d s u b p r o b l e m , n a m e l y t h e s e q u e n c i n g p r o b l e m , i s t o ¯ n d a n
o p t i m a l s e q u e n c e t h a t p r o d u c e s t h e m i n i m u m c o s t p a t h o r t o u r . W i t h r e s p e c t t o t h e s e t w o p r o b l e m s ,
c o n s i d e r t h e f o l l o w i n g a l g o r i t h m f o r G M D H P P :
1 . S o l v i n g t h e p a r t i t i o n i n g p r o b l e m : F i n d a m i n i m u m c o s t f o r e s t w i t h k t r e e s s p a n n i n g a l l t h e d e p o t s
a n d t h e d e s t i n a t i o n s s u c h t h a t t h e r e a r e a t m o s t p n o n - t r i v i a l t r e e s ( a t r e e w i t h a t l e a s t o n e e d g e )
w i t h n o p a t h j o i n i n g a n y t w o d e p o t v e r t i c e s . S i n c e t h e r e a r e k d e p o t v e r t i c e s a n d n o p a t h c a n j o i n a n y
t w o d e p o t v e r t i c e s , t h e r e m u s t b e e x a c t l y o n e d e p o t v e r t e x i n e a c h t r e e o f t h e m i n i m u m c o s t f o r e s t .
T h e d e p o t v e r t i c e s p r e s e n t i n t h e n o n - t r i v i a l t r e e s c o r r e s p o n d t o t h e c h o s e n s a l e s m e n . T h e r e a r e a l -
g o r i t h m s a v a i l a b l e i n t h e l i t e r a t u r e ( [ 7 ] , [ 6 ] , [ 2 1 ] ) t o ¯ n d s u c h a m i n i m u m c o s t f o r e s t i n p o l y n o m i a l t i m e .
1 . G r a d u a t e S t u d e n t , D e p a r t m e n t o f C i v i l E n g i n e e r i n g , U n i v e r s i t y o f C a l i f o r n i a , B e r k e l e y , C A 9 4 7 2 0 , c o r r e s p o n d i n g a u t h o r :
r s i v a @ b e r k e l e y . e d u .
2 . A s s i s t a n t P r o f e s s o r , D e p a r t m e n t o f C i v i l E n g i n e e r i n g , U n i v e r s i t y o f C a l i f o r n i a , B e r k e l e y , C A 9 4 7 2 0 .
1 A n ® ¡ a p p r o x i m a t i o n a l g o r i t h m f o r p r o b l e m P i s a n a l g o r i t h m t h a t
² h a s a p o l y n o m i a l - t i m e r u n n i n g t i m e , a n d
² r e t u r n s a s o l u t i o n w h o s e c o s t i s w i t h i n ® t i m e s t h e o p t i m a l c o s t o f p r o b l e m P .
.
2
2 . S o l v i n g t h e s e q u e n c i n g p r o b l e m : D o u b l e t h e e d g e s i n e a c h n o n t r i v i a l t r e e t o g e t a n E u l e r i a n g r a p h
f o r e a c h c h o s e n s a l e s m a n . S h o r t c u t t h e e d g e s i n e a c h E u l e r i a n g r a p h t o o b t a i n a p a t h f o r e a c h c h o s e n
s a l e s m e n .
I t h a s b e e n s h o w n ( [ 2 1 ] ) t h a t t h e a b o v e a l g o r i t h m h a s a n a p p r o x i m a t i o n r a t i o o f 2 w h e n t h e c o s t s
s a t i s f y t h e t r i a n g l e i n e q u a l i t y . A l s o , u s i n g a s i m i l a r a p p r o a c h , 2 - a p p r o x i m a t i o n a l g o r i t h m s h a v e b e e n
o b t a i n e d f o r o t h e r v a r i a n t s o f t h e m u l t i p l e d e p o t T S P o r H P P a l s o ( [ 1 7 ] , [ 1 8 ] , [ 1 9 ] ) . E x c e p t f o r
t h e 5
3 ¡ a p p r o x i m a t i o n a l g o r i t h m f o r o n e p a r t i c u l a r v a r i a n t o f t h e m u l t i p l e d e p o t H P P , t h e r e a r e n o
a l g o r i t h m s i n t h e l i t e r a t u r e f o r a n y m u l t i p l e d e p o t T S P o r H P P t h a t h a s a n a p p r o x i m a t i o n r a t i o b e t t e r
t h a n 2 . I n t h e f o l l o w i n g s u b s e c t i o n , w e r e v i e w t h i s v a r i a n t a n d i t s a p p r o x i m a t i o n a l g o r i t h m .
A . R e v i e w o f t h e 5
3 - a p p r o x i m a t i o n a l g o r i t h m
T h e p r o b l e m c o n s i d e r e d i n [ 2 0 ] w a s a M u l t i p l e D e p o t , T e r m i n a l H a m i l t o n i a n P a t h P r o b l e m ( M D T H P P )
s t a t e d a s f o l l o w s : G i v e n k s a l e s m e n t h a t s t a r t a t k d i s t i n c t d e p o t v e r t i c e s , k t e r m i n a l v e r t i c e s a n d
n ( ¸ k ) d e s t i n a t i o n v e r t i c e s , t h e p r o b l e m i s t o c h o o s e p a t h s f o r e a c h o f t h e s a l e s m e n s o t h a t ( 1 )
e a c h s a l e s m a n s t a r t s a t h i s r e s p e c t i v e d e p o t v e r t e x , v i s i t s a t l e a s t o n e d e s t i n a t i o n v e r t e x a n d r e a c h e s
a n y o n e o f t h e t e r m i n a l v e r t i c e s n o t v i s i t e d b y o t h e r s a l e s m e n , ( 2 ) e a c h d e s t i n a t i o n v e r t e x i s v i s i t e d
e x a c t l y o n c e a n d ( 3 ) t h e c o s t o f t h e p a t h s i s a m i n i m u m a m o n g a l l p o s s i b l e p a t h s f o r t h e s a l e s m e n .
T h e c r i t e r i a f o r t h e c o s t o f p a t h s c o n s i d e r e d i s t h e t o t a l c o s t o f t h e e d g e s t r a v e l e d b y t h e e n t i r e c o l -
l e c t i o n . T h e s i n g l e d e p o t , s i n g l e t e r m i n a l v e r s i o n w i t h o n e s a l e s m a n c o r r e s p o n d i n g t o t h e M D T H P P
h a s a 5
3 ¡ a p p r o x i m a t i o n a l g o r i t h m b y H o o g e v e e n [ 1 2 ] . T h e 5
3 ¡ a p p r o x i m a t i o n a l g o r i t h m i n [ 2 0 ] f o r
M D T H P P u s e d t h e f o l l o w i n g a p p r o a c h :
1 . S o l v i n g t h e p a r t i t i o n i n g p r o b l e m : F o r m u l a t e t h e M D T H P P a s a m i n i m u m c o s t f o r e s t p r o b l e m s u b j e c t
t o d e g r e e c o n s t r a i n t s o n a l l t h e v e r t i c e s . P e n a l i z e t h e d e g r e e c o n s t r a i n t s t o o b t a i n a c o r r e s p o n d i n g
L a g r a n g i a n d u a l p r o b l e m . S o l v e t h i s L a g r a n g i a n d u a l p r o b l e m t o o b t a i n a m i n i m u m c o s t f o r e s t . A
d e s t i n a t i o n ( o r a t e r m i n a l ) i s a s s i g n e d t o t h e d e p o t ( o r t h e s a l e s m a n l o c a t e d a t t h e d e p o t ) i f i t i s
c o n n e c t e d t o t h e d e p o t i n t h e m i n i m u m c o s t f o r e s t . T h i s s t e p s o l v e s t h e p a r t i t i o n i n g p r o b l e m b y
a s s i g n i n g a s e t o f d e s t i n a t i o n s a n d a t e r m i n a l f o r e a c h s a l e s m a n l o c a t e d a t t h e d e p o t s .
2 . S o l v i n g t h e s e q u e n c i n g p r o b l e m : U s e H o o g e v e e n ' s a l g o r i t h m [ 1 2 ] a v a i l a b l e f o r t h e s i n g l e d e p o t , s i n g l e
t e r m i n a l H P P o n e a c h p a r t i t i o n t o o b t a i n a p a t h f o r e a c h s a l e s m a n .
T h e 5
3 ¡ a p p r o x i m a t i o n r a t i o c o u l d b e p r o v e d b e c a u s e t h e p a r t i t i o n i n g p r o b l e m w a s a d d r e s s e d b y
s o l v i n g a L a g r a n g i a n d u a l p r o b l e m o f t h e M D T H P P . T h e a p p r o x i m a t i o n a l g o r i t h m p r e s e n t e d i n t h i s
p a p e r f o r G M D H P P i s s i m i l a r t o t h e 5
3 ¡ a p p r o x i m a t i o n a l g o r i t h m p r e s e n t e d f o r t h e M D T H P P . H o w -
e v e r , t h e t e c h n i q u e s r e q u i r e d t o s h o w t h e a p p r o x i m a t i o n r a t i o a r e d i ® e r e n t . I n t h e f o l l o w i n g s u b s e c t i o n ,
w e p r e s e n t t h e o u t l i n e o f t h e 3
2 ¡ a p p r o x i m a t i o n a l g o r i t h m f o r G M D H P P .
B . O u r a p p r o a c h
W e f o r m u l a t e G M D H P P a s a m i n i m u m c o s t c o n s t r a i n e d f o r e s t p r o b l e m w i t h a d d e d d e g r e e c o n -
s t r a i n t s o n t h e v e r t i c e s ( s e c t i o n ( I I ) ) . B y d u a l i z i n g t h e d e g r e e c o n s t r a i n t s , w e o b t a i n a L a g r a n g i a n
d u a l f o r t h e G M D H P P ( e q u a t i o n ( 1 4 ) ) . W e ¯ r s t s h o w t h a t t h i s L a g r a n g i a n d u a l p r o b l e m c a n b e s o l v e d
i n p o l y n o m i a l t i m e u s i n g t h e E l l i p s o i d m e t h o d ( P r o p o s i t i o n I I . 2 ) . B y s o l v i n g t h e L a g r a n g i a n d u a l f o r
t h e M D T H P P , w e ¯ n d a s u b s e t o f d e s t i n a t i o n v e r t i c e s f o r e a c h s a l e s m a n t o v i s i t . F o r e a c h i = 1 ; : : ; k ,
w e u s e H o o g e v e e n ' s a l g o r i t h m [ 1 2 ] t o ¯ n d a p a t h f o r a l l t h e s a l e s m e n w h o h a v e a t l e a s t o n e d e s t i n a t i o n
v e r t e x t o v i s i t a s f o l l o w s :
1 . F i n d t h e m i n i m u m c o s t s p a n n i n g t r e e ( T i ) c o r r e s p o n d i n g t o t h e v e r t i c e s o f t h e i t h s a l e s m a n .
2 . F i n d t h e m i n i m u m c o s t p e r f e c t m a t c h i n g ( M i ) o n t h e w r o n g d e g r e e v e r t i c e s p r e s e n t i n T i . A v e r t e x
h a s a w r o n g d e g r e e i f
² i t i s a d e s t i n a t i o n v e r t e x a n d i t s d e g r e e i s o d d .
² i t i s a d e p o t v e r t e x a n d i t s d e g r e e i s e v e n .
3
3 . A d d t h e e d g e s o f M i t o T i t o g e t a n e w g r a p h f o r t h e i t h s a l e s m a n . S h o r t c u t t h e e d g e s i n t h e n e w
g r a p h t o g e t a p a t h f o r t h e i t h s a l e s m a n .
F i r s t , t h e t o t a l c o s t o f a l l t h e m i n i m u m s p a n n i n g t r e e s f o u n d i n s t e p ( 1 ) o f t h e H o o g e v e e n ' s a l g o r i t h m
i s s h o w n t o b e b o u n d e d b y t h e o p t i m a l c o s t o f G M D H P P ( P r o p o s i t i o n I V . 1 ) . A n o t h e r c r u c i a l p a r t o f
o b t a i n i n g a 3
2 ¡ a p p r o x i m a t i o n a l g o r i t h m i s d u e t o P r o p o s i t i o n I V . 5 . P r o p o s i t i o n I V . 5 u p p e r b o u n d s t h e
t o t a l c o s t o f m a t c h i n g b y h a l f t h e o p t i m a l c o s t o f G M D H P P i f t h e c o s t s s a t i s f y t h e t r i a n g l e i n e q u a l i t y .
T h i s h e l p s u s p r o v e t h a t t h e a l g o r i t h m p r e s e n t e d a b o v e f o r G M D H P P h a s a 3
2 ¡ a p p r o x i m a t i o n r a t i o .
T o s h o w t h e u p p e r b o u n d o f t h e t o t a l c o s t o f m a t c h i n g , w e a l s o h a d t o p r o v e t h e f o l l o w i n g r e s u l t :
² F o r a s i n g l e s a l e s m a n , S i n g l e D e p o t H P P ( S D H P P ) , t h e c o s t o f m a t c h i n g u s i n g t h e H o o g e v e e n ' s
a l g o r i t h m i s a t m o s t h a l f t h e o p t i m a l L P r e l a x a t i o n c o s t o f t h e S D H P P i f t h e c o s t s s a t i s f y t h e t r i a n g l e
i n e q u a l i t y ( P r o p o s i t i o n I V . 4 ) . A s i m i l a r r e s u l t h a s a l r e a d y b e e n s h o w n f o r t h e s i n g l e T S P b y W o l s e y
[ 2 4 ] , S h m o y s a n d W i l l i a m s o n [ 2 3 ] . I n t h i s p a p e r , w e a d a p t t h e p r o o f o f S h m o y s a n d W i l l i a m s o n [ 2 3 ]
t o p r o v e a s i m i l a r r e s u l t f o r t h e S D H P P .
I I . P r o b l e m f o r m u l a t i o n
L e t D = f 1 ; 2 ; 3 ; ¢ ¢ ¢ ; k g b e t h e s e t o f v e r t i c e s r e p r e s e n t i n g a l l t h e d e p o t s . T h e r e i s o n e s a l e s m a n
l o c a t e d a t e a c h d e p o t . L e t U = f k + 1 ; k + 2 ; k + 3 ; ¢ ¢ ¢ ; k + n g b e t h e s e t o f v e r t i c e s d e n o t i n g n
d e s t i n a t i o n s . L e t V : = D S U . S i n c e w e a r e c o n s i d e r i n g a m u l t i p l e d e p o t p r o b l e m , l e t k ¸ 2 . W e a l s o
a s s u m e t h e r e a r e a t l e a s t t h r e e d e s t i n a t i o n v e r t i c e s ( n ¸ 3 ) t o e l i m i n a t e t r i v i a l c a s e s . L e t p d e n o t e
t h e m a x i m u m n u m b e r o f s a l e s m e n t h a t c o u l d c h o s e n f o r v i s i t i n g a l l t h e d e s t i n a t i o n s . T h e e d g e j o i n i n g
v e r t i c e s i a n d j h a s a c o s t C i j 2 Q + a s s o c i a t e d w i t h i t w h e r e Q + i s t h e s e t o f a l l p o s i t i v e r a t i o n a l
n u m b e r s . A s s u m e t h a t a l l c o s t s a r e p o s i t i v e a n d s y m m e t r i c , i . e . , C i j > 0 a n d C i j = C j i f o r a l l i ; j 2 V .
L e t C m i n = m i n i ; j 2 V ; i < j C i j a n d C m a x = m a x i ; j 2 V ; i < j C i j . C m i n > 0 b y a s s u m p t i o n . T o s i m p l i f y t h e
n o t a t i o n i n t h e l a t e r s t a g e s , t h e G M D H P P i s d e ¯ n e d f o r a s e t o f v e r t i c e s , S µ V . L e t D S a n d U S
d e n o t e t h e s e t o f a l l t h e d e p o t s a n d d e s t i n a t i o n s p r e s e n t i n S r e s p e c t i v e l y ( i . e . D S = S T f 1 ; 2 ; ¢ ¢ ¢ ; k g ,
U S = S T f k + 1 ; k + 2 ; ¢ ¢ ¢ ; n g ) . D e c i s i o n v a r i a b l e x i j i s u s e d t o r e p r e s e n t t h e c h o i c e o f t h e e d g e b e t w e e n
v e r t e x i a n d j f o r a l l i ; j 2 S . x i j = 1 i m p l i e s t h e e d g e j o i n i n g v e r t e x i a n d v e r t e x j i s c h o s e n a n d
x i j = 0 o t h e r w i s e . L e t t h e v a r i a b l e s x i j 8 i ; j 2 S ; i < j b e t e r s e l y d e n o t e d a s x . F o r a g i v e n S µ V
w i t h j D S j ¸ 1 , t h e G M D H P P i s f o r m u l a t e d a s f o l l o w s :
C o p t
S = m i n
x X i 2 S ; j 2 S ; i < j
C i j x i j ( 1 )
X j 2 U S
x i j · 1 f o r a l l i 2 D S ; ( 2 )
X j 2 S ; i < j
x i j + X j 2 S ; j < i
x j i · 2 f o r a l l i 2 U S ; ( 3 )
X i 2 D S j 2 U S ; i < j
x i j · p ; ( 4 )
X i 2 S ; j 2 S ; i < j
x i j = j U S j ; ( 5 )
X i 2 R ; j 2 R ; i < j
x i j · j R j ¡ 1 ; f o r a l l R µ S ; ( 6 )
X i 2 R ; j 2 R ; i < j
x i j · j R j ¡ 2 ; f o r a l l R s u c h t h a t R µ S a n d j R \ D S j = 2 ; ( 7 )
x i j 2 f 0 ; 1 g , f o r a l l i ; j 2 S ; i < j : ( 8 )
4
C o p t
S d e n o t e s t h e o p t i m a l c o s t o f t h e G M D H P P c o r r e s p o n d i n g t o t h e s e t o f v e r t i c e s S µ V . E q u a t i o n
( 2 ) s t a t e s t h a t t h e d e g r e e o f e a c h d e p o t v e r t e x m u s t b e a t m o s t 1 . E q u a t i o n ( 3 ) r e q u i r e s t h a t t h e
d e g r e e o f e a c h d e s t i n a t i o n v e r t e x m u s t b e a t m o s t 2 . E q u a t i o n ( 4 ) s t a t e s t h a t a t m o s t p s a l e s m e n
c a n b e u s e d f o r v i s i t i n g a l l t h e d e s t i n a t i o n s . E q u a t i o n ( 5 ) s t a t e s t h a t t h e t o t a l n u m b e r o f e d g e s i n
a n y f e a s i b l e s o l u t i o n t o t h e G M D H P P m u s t b e e q u a l t o j U S j ( i . e t h e r e a r e j D S j t r e e s ) . E q u a t i o n ( 6 )
e l i m i n a t e s t h e p r e s e n c e o f a c y c l e i n a n y f e a s i b l e s o l u t i o n . E q u a t i o n ( 7 ) e l i m i n a t e s t h e p o s s i b i l i t y o f a
p a t h j o i n i n g a n y t w o d e p o t v e r t i c e s i n D S .
L e t e q u a t i o n s ( 2 ) , ( 3 ) b e w r i t t e n a s A 1
S x · B 1 S
a n d ( 4 ) - ( 7 ) b e w r i t t e n a s A 2
S x · B 2 S
. D e ¯ n e P ( S ) : =
f x : A 1
S x · B 1 S
; A 2
S x · B 2 S
; x ¸ 0 g . y i s a f e a s i b l e s o l u t i o n t o t h e G M D H P P i f y i s p r e s e n t i n
f x : x 2 P ( S ) ; x i s a n i n t e g e r g . T h e G M D H P P c a n n o w b e r e s t a t e d a s
C o p t
S = m i n
x f C S ( x ) : x 2 P ( S ) ; x i s a n i n t e g e r g ; ( 9 )
w h e r e C S ( x ) = P i 2 S ; j 2 S ; i < j C i j x i j . T h e L P r e l a x a t i o n o f t h i s p r o b l e m i s :
C l p
S = m i n
x f C S ( x ) : x 2 P ( S ) g : ( 1 0 )
I n t h e a b o v e e q u a t i o n , C l p
S d e n o t e s t h e o p t i m a l L P r e l a x a t i o n c o s t o f t h e G M D H P P d e ¯ n e d f o r t h e
s e t o f v e r t i c e s S µ V .
I n t h e f o l l o w i n g d i s c u s s i o n , w e s h o w h o w t h e G M D H P P f o r m u l a t e d i n e q u a t i o n s ( 1 - 8 ) c a n b e v i e w e d
a s a c o n s t r a i n e d f o r e s t p r o b l e m w i t h d e g r e e c o n s t r a i n t s o n a l l t h e v e r t i c e s . I n t h i s p a p e r , a c o n s t r a i n e d
f o r e s t f o r a g i v e n s e t o f v e r t i c e s S w i t h j D S j ¸ 1 i s d e ¯ n e d a s a f o r e s t w i t h t h e f o l l o w i n g c o n s t r a i n t s :
² t h e r e a r e e x a c t l y j D S j t r e e s s u c h t h a t n o t w o d e p o t v e r t i c e s a r e c o n n e c t e d , a n d
² t h e r e a r e a t m o s t p e d g e s j o i n i n g a n y v e r t e x i n D S t o a n y v e r t e x i n U S .
E q u a t i o n s ( 4 - 8 ) d e s c r i b e a l l t h e c o n s t r a i n t s m e n t i o n e d a b o v e . S i n c e t h e f o r e s t h a s e x a c t l y j D S j t r e e s
a n d n o t w o d e p o t v e r t i c e s m u s t b e c o n n e c t e d , e a c h t r e e m u s t c o n t a i n e x a c t l y o n e d e p o t v e r t e x . T h e
c o n s t r a i n e d f o r e s t p r o b l e m , d e n o t e d b y C F , i s :
C f
S = m i n
x f C S ( x ) : x 2 F ( S ) ; x i s a n i n t e g e r g ; ( 1 1 )
w h e r e ,
F ( S ) = f x : A 2
S x · B 2 S ; x ¸ 0 g : ( 1 2 )
I n t h e a b o v e e q u a t i o n s , C f
S d e n o t e s t h e o p t i m a l c o s t o f t h e c o n s t r a i n e d f o r e s t p r o b l e m d e ¯ n e d f o r
t h e s e t o f v e r t i c e s S µ V . T h i s c o n s t r a i n e d f o r e s t p r o b l e m c a n b e s o l v e d i n p o l y n o m i a l t i m e u s i n g
t h e a l g o r i t h m s i n [ 7 ] , [ 6 ] o r [ 2 1 ] . T h e G M D H P P i s a c t u a l l y C F w i t h t h e a d d i t i o n a l d e g r e e c o n s t r a i n t s
p r e s e n t i n A 1
S x · B 1 S
. B e f o r e w e p r e s e n t t h e a p p r o x i m a t i o n a l g o r i t h m f o r G M D H P P i n t h e n e x t
s e c t i o n , w e f o r m u l a t e a L a g r a n g i a n d u a l p r o b l e m c o r r e s p o n d i n g t o G M D H P P a n d s h o w i t s r e l a t e d
r e s u l t s t h a t a r e c r u c i a l i n p r o v i n g t h e a p p r o x i m a t i o n r a t i o .
G i v e n a c o n s t r a i n e d f o r e s t x , l e t d i ( x ; S ) d e n o t e t h e d e g r e e o f v e r t e x i i n S . T h a t i s ,
d i ( x ; S ) = ½ P j 2 U S
x i j f o r a l l i 2 D S ; P j 2 S ; i < j x i j + P j 2 S ; j < i x j i f o r a l l i 2 U S :
( 1 3 )
B y d u a l i z i n g t h e c o n s t r a i n t s i n A 1
S x · B 1 S
, w e c a n o b t a i n a L a g r a n g i a n d u a l t o t h e G M D H P P . T h i s
L a g r a n g i a n d u a l p r o b l e m f o r a g i v e n s e t S µ V c a n b e f o r m u l a t e d a s m a x ¼ ¸ 0 w ( ¼ ; S ) w h e r e
5
w ( ¼ ; S ) = m i n
x 2 F ( S ) ; x i s a n i n t e g e r
[ C S ( x ) + X i 2 D S
¼ i ( d i ( x ; S ) ¡ 1 ) + X i 2 U S
¼ i ( d i ( x ; S ) ¡ 2 ) ] :
I n t h e a b o v e e q u a t i o n , ¼ i i s t h e p e n a l i z i n g v a r i a b l e c o r r e s p o n d i n g t o t h e d e g r e e c o n s t r a i n t o f t h e i t h
v e r t e x . A l s o , l e t ¼ i n d i c a t e t h e p e n a l i z i n g v a r i a b l e s ¼ i f o r a l l i 2 S . B y l e t t i n g
v i ( x ; S ) = ½ d i ( x ; S ) ¡ 1 i f i 2 D S ;
d i ( x ; S ) ¡ 2 i f i 2 U S ;
w e r e s t a t e t h e L a g r a n g i a n d u a l p r o b l e m f o r a g i v e n S µ V a s
m a x
¼ ¸ 0
w ( ¼ ; S )
w h e r e ,
w ( ¼ ; S ) = m i n
x 2 F ( S ) ; x i s a n i n t e g e r
[ C S ( x ) + X i 2 S
¼ i v i ( x ; S ) ] : ( 1 4 )
W e ¯ r s t s t a t e a r e s u l t t h a t r e l a t e s C l p
S ( t h e o p t i m a l L P r e l a x a t i o n c o s t ) , m a x ¼ ¸ 0 w ( ¼ ; S ) ( t h e o p t i m a l
L a g r a n g i a n d u a l c o s t ) a n d C o p t
S ( t h e o p t i m a l i n t e g e r p r o g r a m m i n g c o s t ) .
P r o p o s i t i o n I I . 1 : F o r a n y S µ V w i t h j D S j ¸ 1 ,
C l p
S · m a x
¼ ¸ 0
w ( ¼ ; S ) · C o p t
S : ( 1 5 )
P r o o f : T h i s f o l l o w s f r o m a k n o w n r e s u l t f o r i n t e g e r p r o g r a m s . R e f e r t o p a g e 1 3 i n F i s h e r [ 5 ] o r
p a g e 3 3 0 i n N e m h a u s e r a n d W o l s e y [ 1 5 ] . I n g e n e r a l , f o r i n t e g e r p r o g r a m s w i t h m i n i m i z a t i o n o b j e c t i v e ,
t h e o p t i m a l L a g r a n g i a n d u a l c o s t c a n a t m o s t b e e q u a l t o t h e o p t i m a l i n t e g e r p r o g r a m m i n g c o s t . A l s o ,
t h e o p t i m a l L P r e l a x a t i o n c o s t c a n a t m o s t b e e q u a l t o t h e o p t i m a l L a g r a n g i a n d u a l c o s t .
P r o p o s i t i o n I I . 2 : T h e L a g r a n g i a n d u a l p r o b l e m , m a x ¼ ¸ 0 w ( ¼ ; V ) , c a n b e s o l v e d i n t i m e p o l y n o m i a l
i n n + k a n d l o g n C m a x u s i n g t h e E l l i p s o i d m e t h o d .
P r o o f : T h i s t h e o r e m i s p r o v e n u s i n g t h e r e s u l t s i n G r o t s c h e l e t a l . [ 8 ] . T h e L a g r a n g i a n d u a l
p r o b l e m , m a x ¼ ¸ 0 w ( ¼ ; V ) , c a n a l s o b e w r i t t e n a s a l i n e a r p r o g r a m a s f o l l o w s :
m a x
t ; ¼ ¸ 0
t
t · C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ; 8 x w h e r e x i s a c o n s t r a i n e d f o r e s t : ( 1 6 )
U s i n g L e m m a V . 1 p r o v e d i n t h e a p p e n d i x , a d d i n g t h e c o n s t r a i n t s 0 · t · n C m a x a n d 0 · ¼ i · n C m a x 8 i 2 V t o t h e l i n e a r p r o g r a m a b o v e d o e s n o t c h a n g e i t s o p t i m a l c o s t . N o w , d e ¯ n e
P : = f t ; ¼ : t · C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ; 8 x w h e r e x i s a c o n s t r a i n e d f o r e s t ;
0 · t · n C m a x ;
0 · ¼ i · n C m a x 8 i 2 V g :
( 1 7 )
6
T o s h o w t h a t t h e l i n e a r p r o g r a m ( 1 6 ) i s s o l v a b l e u s i n g t h e E l l i p s o i d m e t h o d , w e n e e d t o s h o w t h e
f o l l o w i n g :
² T h e f o l l o w i n g s e p a r a t i o n p r o b l e m i s s o l v a b l e i n p o l y n o m i a l t i m e :
G i v e n a n y t ¤ 2 Q a n d ¼ ¤ 2 Q j V j , d e c i d e w h e t h e r t ¤ ; ¼ ¤ 2 P a n d i f n o t ¯ n d a v i o l a t e d c o n s t r a i n t .
² L e t B ( y ; ½ ) f o r y 2 R j V j + 1 ; ½ 2 R + b e a b a l l o f r a d i u s ½ c e n t e r e d a t y w h e r e R d e n o t e s t h e s e t o f a l l
r e a l n u m b e r s . T h e r e e x i s t s y 1 ; y 2 2 R j V j + 1 a n d ½ 1 ; ½ 2 2 R + w h e r e l o g ½ 1 ; l o g ½ 2 a r e p o l y n o m i a l f u n c t i o n s
o f t h e i n p u t s u c h t h a t B ( y 1 ; ½ 1 ) µ P µ B ( y 2 ; ½ 2 ) .
S i n c e t h e c o n s t r a i n e d f o r e s t p r o b l e m i s s o l v a b l e i n p o l y n o m i a l t i m e ( [ 7 ] , [ 6 ] , [ 2 1 ] ) , w e k n o w t h a t
t h e s e p a r a t i o n p r o b l e m i s s o l v a b l e i n p o l y n o m i a l t i m e . T o s h o w t h a t a b a l l i s c o n t a i n e d i n P c h o o s e
t o = C m i n
n + k , ¼ o
i = C m i n
n + k 8 i 2 V a n d ½ 1 = C m i n
n + k . C m i n > 0 b y a s s u m p t i o n . L e t t h e c e n t e r o f t h e b a l l b e
y 1 = ( t o ; ¼ o
1 ; ¢ ¢ ¢ ; ¼ o n
+ k ) . L e m m a V . 2 i n t h e a p p e n d i x p r o v e s t h a t B ( y 1 ; ½ 1 ) µ P . A s i n t h e d e ¯ n i t i o n
o f P , a l l t h e v a r i a b l e s , ( t ; ¼ 1 ; ¢ ¢ ¢ ; ¼ n + k ) , a r e p o s i t i v e a n d u p p e r b o u n d e d b y n C m a x . T h e r e f o r e b y
c h o o s i n g ½ 2 = n C m a x , o n e c a n c o n c l u d e t h a t P µ B ( 0 ; ½ 2 ) .
S i n c e P i s f u l l d i m e n s i o n a l , b o u n d e d a n d t h e s e p a r a t i o n p r o b l e m i s s o l v a b l e i n p o l y n o m i a l t i m e , o n e
c a n u s e t h e r e s u l t s i n G r o t s c h e l e t a l . [ 8 ] t o c o n c l u d e t h a t t h e l i n e a r p r o g r a m f o r m u l a t e d i n ( 1 6 ) i s
s o l v a b l e i n t i m e p o l y n o m i a l i n t h e n u m b e r o f v e r t i c e s ( i . e . n + k ) a n d l o g ½ 2 ( i . e . l o g n C m a x ) u s i n g t h e
E l l i p s o i d m e t h o d .
W e n o w s t a t e a r e s u l t r e g a r d i n g t h e d e c o m p o s i t i o n o f t h e o p t i m a l L a g r a n g i a n d u a l c o s t o f t h e
G M D H P P . A s i m i l a r r e s u l t w a s a l s o s h o w n f o r a d i ® e r e n t m u l t i p l e d e p o t , t e r m i n a l H P P i n [ 2 0 ] .
P r o p o s i t i o n I I . 3 : L e t ( ¼ ¤ ; x ¤ ) s o l v e t h e L a g r a n g i a n d u a l p r o b l e m , m a x ¼ ¸ 0 w ( ¼ ; V ) , w h e r e
w ( ¼ ; V ) = m i n
x 2 F ( V ) ; x i s a n i n t e g e r
[ C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ] :
L e t P i ( x ¤ ) b e t h e s e t o f a l l v e r t i c e s p r e s e n t i n t h e i t h t r e e o f t h e o p t i m a l s o l u t i o n x ¤ . T h e n ,
m a x
¼ ¸ 0
w ( ¼ ; V ) = X m = 1 ; ¢ ¢ ¢ ; k
m a x
¼ m ¸ 0
w ( ¼ m ; P m ( x ¤ ) ) ;
w h e r e ¼ m r e p r e s e n t s ¼ i f o r a l l i 2 P m ( x ¤ ) .
P r o o f : R e f e r t o t h e a p p e n d i x .
I I I . A p p r o x i m a t i o n a l g o r i t h m f o r G M D H P P
W e g e n e r a t e a f e a s i b l e s o l u t i o n , x a p p r o x , f o r t h e G M D H P P u s i n g t h e f o l l o w i n g a l g o r i t h m c a l l e d
a p p r o x :
² S o l v e t h e L a g r a n g i a n d u a l p r o b l e m ,
m a x
¼ ¸ 0
m i n
x 2 F ( V ) ; x i s a n i n t e g e r
[ C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ]
u s i n g t h e E l l i p s o i d m e t h o d . L e t ( ¼ ¤ ; x ¤ ) b e t h e c o r r e s p o n d i n g o p t i m a l s o l u t i o n . x ¤ i s a d i s j o i n t f o r e s t
w i t h k t r e e s s u c h t h a t a d e p o t v e r t e x i s c o n t a i n e d i n e a c h t r e e . L e t P i ( x ¤ ) b e t h e s e t o f v e r t i c e s p r e s e n t
i n t h e i t h t r e e . N o t e t h a t P i ( x ¤ ) T P j ( x ¤ ) = ; f o r i 6 = j a n d S i 2 1 ; ¢ ¢ ¢ ; k P i ( x ¤ ) = V . L e t t h e d e p o t v e r t e x
p r e s e n t i n P i ( x ¤ ) b e d e n o t e d a s r i . W e u s e H o o g e v e e n ' s a p p r o x i m a t i o n a l g o r i t h m [ 1 2 ] t o c o n s t r u c t a
p a t h f o r e a c h s a l e s m a n i 2 f 1 ; ¢ ¢ ¢ ; k g a s f o l l o w s :
1 . I f j P i ( x ¤ ) j = 1 , t h e n P i ( x ¤ ) i s a t r i v i a l c o m p o n e n t a n d c o n t a i n s o n l y t h e d e p o t v e r t e x r i . H e n c e ,
w e n e e d n o t p r o c e e d f u r t h e r f o r t h i s c o m p o n e n t .
2 . F i n d t h e m i n i m u m s p a n n i n g t r e e T i c o r r e s p o n d i n g t o t h e v e r t i c e s i n P i ( x ¤ ) .
7
3 . F i n d t h e s e t o f o d d d e g r e e v e r t i c e s S i o f T i . N o t e t h a t t h e n u m b e r o f o d d d e g r e e v e r t i c e s j S i j i s
e v e n .
4 . I f t h e d e p o t v e r t e x r i p r e s e n t i n T i h a s e v e n d e g r e e , t h e n l e t S i : = S i S f r i g e l s e l e t S i : = S i n f r i g .
5 . F i n d t h e m i n i m u m c o s t m a t c h i n g M i o n S i o f c a r d i n a l i t y j S i j ¡ 1
2 .
6 . N o w c o n s i d e r t h e g r a p h G i = ( P i ( x ¤ ) ; E i ) w h e r e E i i s t h e u n i o n o f a l l t h e e d g e s p r e s e n t i n T i a n d
M i . G i i s c o n n e c t e d a n d h a s e i t h e r 0 o r 2 o d d d e g r e e v e r t i c e s .
{ I f t h e r e a r e 2 o d d d e g r e e v e r t i c e s , t h e n o n e o f t h e 2 o d d d e g r e e v e r t i c e s m u s t b e t h e d e p o t v e r t e x
r i .
{ I f t h e r e a r e 0 o d d d e g r e e v e r t i c e s , t h e n r e m o v e a n e d g e e i j o i n i n g t h e d e p o t v e r t e x r i t o a n y o t h e r
v e r t e x i n P i ( x ¤ ) . T h e n t h e r e s u l t i n g g r a p h G i = ( P i ( x ¤ ) ; E i n f e i g ) w o u l d h a v e t w o o d d d e g r e e v e r t i c e s
w i t h t h e d e p o t v e r t e x b e i n g o n e o f t h e m .
7 . C o n s t r u c t a n E u l e r i a n p a t h t h a t t r a v e r s e s e a c h e d g e i n G i e x a c t l y o n c e . T h e E u l e r i a n p a t h w i l l
h a v e t h e t w o o d d d e g r e e v e r t i c e s a s i t s e n d p o i n t s . T h i s c o n s t r u c t i o n c a n b e d o n e u s i n g t h e a l g o r i t h m s
g i v e n i n [ 1 2 ] , [ 2 5 ] .
8 . S h o r t c u t t h i s E u l e r i a n p a t h t o p r o d u c e a H a m i l t o n i a n p a t h s t a r t i n g a t d e p o t v e r t e x r i a n d v i s i t i n g
a l l t h e v e r t i c e s p r e s e n t i n P i ( x ¤ ) . I f t h e c o s t s s a t i s f y t h e t r i a n g l e i n e q u a l i t y , t h e c o s t o f t h i s H a m i l t o n i a n
p a t h w i l l b e l e s s t h a n o r e q u a l t o t h e c o s t o f t h e E u l e r i a n p a t h .
T h e f o l l o w i n g i s t h e m a i n r e s u l t o f t h i s p a p e r :
T h e o r e m I I I . 1 : L e t t h e c o s t s b e s y m m e t r i c a n d s a t i s f y t h e t r i a n g l e i n e q u a l i t y . A l g o r i t h m a p p r o x
p r o v i d e s a f e a s i b l e s o l u t i o n , x a p p r o x , w i t h a n a p p r o x i m a t i o n r a t i o o f 3
2 f o r G M D H P P a n d i s s o l v a b l e i n
t i m e p o l y n o m i a l i n n + k a n d l o g n C m a x .
I V . P r o o f o f t h e o r e m I I I . 1
T h e c o m p u t a t i o n a l c o m p l e x i t y o f a l g o r i t h m a p p r o x i s d o m i n a t e d b y t h e E l l i p s o i d m e t h o d w h i c h
i s s o l v a b l e i n t i m e p o l y n o m i a l i n n + k a n d l o g n C m a x b y P r o p o s i t i o n I I . 2 . T h e r e s t o f t h e s e c t i o n
c o n s t r u c t s t h e n e c e s s a r y r e s u l t s t o p r o v e t h e f o l l o w i n g :
I f t h e c o s t s s a t i s f y t h e t r i a n g l e i n e q u a l i t y , t h e n
C o p t
V · X i ; j 2 V ; i < j
C i j x a p p r o x
i j ·
3
2
C l p
V :
T h e t o t a l c o s t o f t h e f e a s i b l e s o l u t i o n , x a p p r o x , i s u p p e r b o u n d e d b y
X i 2 1 ; ¢ ¢ ¢ ; k
( C ( T i ) + C ( M i ) ) ( 1 8 )
w h e r e C ( T i ) a n d C ( M i ) r e p r e s e n t t h e t o t a l c o s t o f t h e e d g e s p r e s e n t i n T i a n d M i r e s p e c t i v e l y .
P r o p o s i t i o n I V . 1 : ( B o u n d o n t h e c o s t o f s p a n n i n g t r e e s )
X i = 1 ; ¢ ¢ ¢ ; k
C ( T i ) · C o p t
V : ( 1 9 )
P r o o f : P i ( x ¤ ) h a s o n e d e p o t v e r t e x . T h e r e f o r e t h e p a t h e l i m i n a t i o n c o n s t r a i n t s p r e s e n t i n
F ( P i ( x ¤ ) ) b e t w e e n a n y t w o d e p o t v e r t i c e s a r e t r i v i a l l y s a t i s ¯ e d . R e m a i n i n g c o n s t r a i n t s i n F ( P i ( x ¤ ) )
d e s c r i b e t h e s p a n n i n g t r e e c o n s t r a i n t s c o r r e s p o n d i n g t o P i ( x ¤ ) w i t h a d e g r e e c o n s t r a i n t o n t h e d e p o t
v e r t e x r i . S i n c e T i i s t h e m i n i m u m s p a n n i n g t r e e c o r r e s p o n d i n g t o t h e v e r t i c e s i n P i ( x ¤ ) w i t h n o d e g r e e
c o n s t r a i n t s ,
C ( T i ) · m i n
x f C P i ( x ¤ ) ( x ) : x 2 F ( P i ( x ¤ ) ) ; x i s a n i n t e g e r g : ( 2 0 )
L e t ¼ i r e p r e s e n t ¼ j f o r a l l j 2 P i ( x ¤ ) . I f a l l t h e p e n a l i z i n g v a r i a b l e s a r e z e r o ( i : e : ¼ i = 0 ) , t h e n n o t e
t h a t w ( 0 ; P i ( x ¤ ) ) = m i n x f C P i ( x ¤ ) ( x ) : x 2 F ( P i ( x ¤ ) ) ; x i s a n i n t e g e r g b y d e ¯ n i t i o n . T h e r e f o r e ,
8
C ( T i ) · m i n
x f C P i ( x ¤ ) ( x ) : x 2 F ( P i ( x ¤ ) ) ; x i s a n i n t e g e r g
= w ( 0 ; P i ( x ¤ ) )
· m a x
¼ i ¸ 0
w ( ¼ i ; P i ( x ¤ ) ) :
( 2 1 )
F r o m e q u a t i o n ( 2 1 ) a n d P r o p o s i t i o n s I I . 3 , I I . 1 ,
X i = 1 ; ¢ ¢ ¢ ; k
C ( T i ) · X i = 1 ; ¢ ¢ ¢ ; k
m a x
¼ i ¸ 0
w ( ¼ i ; P i ( x ¤ ) )
= m a x
¼ ¸ 0
w ( ¼ ; V )
· C o p t
V :
( 2 2 )
I n t h e f o l l o w i n g s u b s e c t i o n w e s h o w t h a t P i = 1 ; ¢ ¢ ¢ ; k C ( M i ) ) · 1
2 C o p t
V .
A . B o u n d o n t h e c o s t o f m a t c h i n g
W e ¯ r s t s h o w t h a t f o r a s i n g l e s a l e s m a n H P P t h e c o s t o f m a t c h i n g i s u p p e r b o u n d e d b y h a l f t h e
o p t i m a l L P r e l a x a t i o n c o s t o f t h e H P P . C o n s i d e r a m a t c h i n g p r o b l e m o n a s e t o f v e r t i c e s d e n o t e d
b y ¹ V . A s s u m i n g t h a t j ¹ V j i s o d d , t h e o b j e c t i v e o f t h e m i n i m u m c o s t m a t c h i n g p r o b l e m i s t o ¯ n d a
m a t c h i n g M w i t h j ¹ V j ¡ 1
2 e d g e s t h a t h a s m i n i m u m c o s t . D u e t o E d m o n d s ( 1 9 6 5 ) , t h i s m a t c h i n g p r o b l e m
c a n b e f o r m u l a t e d a s a l i n e a r p r o g r a m a s f o l l o w s :
C ( M ) : = m i n X i 2 ¹ V ; j 2 ¹ V ; i < j
C i j x i j
X j 2 ¹ V ; i < j
x i j + X j 2 ¹ V ; j < i
x j i · 1 f o r a l l i 2 ¹ V ;
X i 2 ¹ V ; j 2 ¹ V ; i < j
x i j = j ¹ V j ¡ 1
2
;
X i 2 R ; j 2 R ; i < j
x i j · j R j ¡ 1
2
; f o r a l l R ½ ¹ V ; j R j ¸ 3 ; j R j o d d ;
0 · x i j · 1 f o r a l l i ; j 2 ¹ V ; i < j :
( 2 3 )
N o w , c o n s i d e r t h e H a m i l t o n i a n p a t h p r o b l e m o f ¯ n d i n g a m i n i m u m c o s t p a t h t h a t v i s i t s e a c h v e r t e x
i n ¹ V e x a c t l y o n c e . I n t h i s p a t h p r o b l e m n o t e t h a t t h e s t a r t o r t h e e n d v e r t e x o f t h e p a t h i s n o t
s p e c i ¯ e d . A i n t e g e r p r o g r a m m i n g f o r m u l a t i o n o f t h i s H a m i l t o n i a n p a t h p r o b l e m i s
m i n X i 2 ¹ V ; j 2 ¹ V ; i < j
C i j x i j ( 2 4 )
9
X j 2 ¹ V ; i < j
x i j + X j 2 ¹ V ; j < i
x j i · 2 f o r a l l i 2 ¹ V ; ( 2 5 )
X i 2 ¹ V ; j 2 ¹ V ; i < j
x i j = j ¹ V j ¡ 1 ; ( 2 6 )
X i 2 R ; j 2 R ; i < j
x i j ; · j R j ¡ 1 ; f o r a l l R µ ¹ V ; ( 2 7 )
x i j 2 f 0 ; 1 g f o r a l l i ; j 2 ¹ V ; i < j : ( 2 8 )
( 2 9 )
C o n s i d e r a L P r e l a x a t i o n o f t h e a b o v e p r o b l e m w h e r e t h e c o n s t r a i n t s x i j 2 f 0 ; 1 g 8 i ; j 2 ¹ V ; i < j a r e
r e p l a c e d w i t h x i j ¸ 0 8 i ; j 2 ¹ V ; i < j . L e t C H P P
¹ V b e t h e o p t i m a l c o s t o f t h i s L P r e l a x a t i o n .
P r o p o s i t i o n I V . 2 : C ( M ) · 1
2 C H P P
¹ V :
P r o o f : I f x i s a f e a s i b l e s o l u t i o n t o t h e L P r e l a x a t i o n o f t h e H a m i l t o n i a n P a t h P r o b l e m ( 2 4 - 2 8 ) ,
t h e n x
2 i s a l s o a f e a s i b l e s o l u t i o n t o t h e m a t c h i n g p r o b l e m . H e n c e , C ( M ) · 1
2 C H P P
¹ V :
P r o p o s i t i o n I V . 3 : I f t h e c o s t s s a t i s f y t r i a n g l e i n e q u a l i t y , t h e n f o r a n y ¹ V µ V 0 , C H P P
¹ V · C H P P
V 0 .
P r o o f : A L a g r a n g i a n d u a l t o t h e H P P ( 2 4 - 2 8 ) i s
m a x
¼ ¸ 0
L D ( ¼ ; ¹ V ) ; ( 3 0 )
w h e r e ,
L D ( ¼ ; ¹ V ) = m i n X i 2 ¹ V ; j 2 ¹ V ; i < j
( C i j + ¼ i + ¼ j ) x i j ¡ 2 X i 2 ¹ V
¼ i
X i 2 ¹ V ; j 2 ¹ V ; i < j
x i j = j ¹ V j ¡ 1 ;
X i 2 R ; j 2 R ; i < j
x i j · j R j ¡ 1 ; f o r a l l R µ ¹ V ;
x i j 2 f 0 ; 1 g f o r a l l i ; j 2 ¹ V ; i < j :
( 3 1 )
A l s o , c o n s i d e r t h e i n t e g e r p r o g r a m o f a m i n i m u m s p a n n i n g t r e e p r o b l e m w i t h t h e o b j e c t i v e f o r m u -
l a t e d i n e q u a t i o n ( 2 4 ) a n d t h e c o n s t r a i n t s f o r m u l a t e d i n ( 2 6 - 2 8 ) . I t i s w e l l k n o w n ( L a w l e r [ 1 4 ] ) t h a t
t h e e x t r e m e p o i n t s o f t h e L P r e l a x a t i o n o f t h i s i n t e g e r p r o g r a m i s i n o n e t o o n e c o r r e s p o n d e n c e w i t h
t h e s e t o f t r e e s s p a n n i n g a l l t h e v e r t i c e s i n ¹ V . H e n c e , s o l v i n g t h e L P r e l a x a t i o n i t s e l f p r o d u c e s t h e
o p t i m a l s p a n n i n g t r e e . B e c a u s e o f t h i s i n t e g r a l i t y p r o p e r t y , u s i n g c o r o l l a r y ( 6 . 6 ) i n N e m h a u s e r a n d
W o l s e y [ 1 5 ] o r t h e r e s u l t s i n F i s h e r [ 5 ] , i t f o l l o w s t h a t
m a x
¼ ¸ 0
L D ( ¼ ; ¹ V ) = C H P P
¹ V : ( 3 2 )
N o w , c o n s i d e r t h e H P P o n t h e s e t o f v e r t i c e s V 0 : = ¹ V S f b g . T h e a i m i s t o s h o w t h a t C H P P
¹ V · C H P P
V 0 i f t h e c o s t s s a t i s f y t h e t r i a n g l e i n e q u a l i t y . B y e q u a t i o n ( 3 2 ) , w e e s s e n t i a l l y w a n t t o p r o v e
1 0
t h a t m a x ¼ ¸ 0 L D ( ¼ ; ¹ V ) · m a x ¼ 0 ¸ 0 L D ( ¼ 0 ; V 0 ) . L e t u s p r o v e t h i s b y c o n t r a d i c t i o n . L e t u s a s s u m e
t h a t m a x ¼ ¸ 0 L D ( ¼ ; ¹ V ) > m a x ¼ 0 ¸ 0 L D ( ¼ 0 ; V 0 ) . L e t ¼ ¤ s o l v e m a x ¼ ¸ 0 L D ( ¼ ; ¹ V ) . L e t ¼ b ¸ 0 b e t h e
w e i g h t o n v e r t e x b . L e t ¼ 0 b e s u c h t h a t ¼ 0 i
= ¼ ¤ i f o r i 2 ¹ V a n d ¼ 0 b
= ¼ b . F o r a n y a r b i t r a r y ¼ b ,
m a x ¼ ¸ 0 L D ( ¼ ; ¹ V ) > L D ( ¼ 0 ; V 0 ) b y a s s u m p t i o n . G i v e n ¼ ¤ , l e t a o p t i m a l s p a n n i n g t r e e c o r r e s p o n d i n g
t o t h e m i n i m i z a t i o n p r o b l e m i n L D ( ¼ 0 ; V 0 ) b e d e n o t e d b y T ( ¼ b ) . L e t u s c o n s i d e r t h e f o l l o w i n g t w o c a s e s :
² L e t ¼ b = 0 . T h e r e e x i s t s n o o p t i m a l s p a n n i n g t r e e , T ( 0 ) , w i t h t h e d e g r e e o f v e r t e x b g r e a t e r t h a n 1 :
I n t h i s c a s e , v e r t e x b i s a l e a f i n t h e t r e e T ( 0 ) . L e t b b e c o n n e c t e d t o v e r t e x q i n T ( 0 ) . R e m o v -
i n g t h e e d g e j o i n i n g v e r t e x b a n d q w i l l r e s u l t i n a t r e e , ¹ T = T ( 0 ) n ( b ; q ) , s p a n n i n g t h e v e r t i c e s i n ¹ V .
B y d e ¯ n i t i o n ,
L D ( ¼ 0 ; V 0 ) = X ( i ; j ) 2 T ( 0 )
( C i j + ¼ 0 i
+ ¼ 0 j
) ¡ 2 X i 2 V 0
¼ 0 i
= C b q + ¼ b + ¼ q + X ( i ; j ) 2 ¹ T
( C i j + ¼ 0 i
+ ¼ 0 j
) ¡ 2 X i 2 ¹ V
¼ 0 i
¡ 2 ¼ b
( 3 3 )
S i n c e , ¼ q ¸ 0 a n d ¼ b = 0 , w e g e t ,
L D ( ¼ 0 ; V 0 ) ¸ X ( i ; j ) 2 ¹ T
( C i j + ¼ 0 i
+ ¼ 0 j
) ¡ 2 X i 2 ¹ V
¼ 0 i
= X ( i ; j ) 2 ¹ T
( C i j + ¼ ¤ i + ¼ ¤ j ) ¡ 2 X i 2 ¹ V
¼ ¤ i
¸ m a x
¼ ¸ 0
L D ( ¼ ; ¹ V ) :
( 3 4 )
² L e t ¼ b = 0 . T h e d e g r e e o f v e r t e x b i n e v e r y o p t i m a l s p a n n i n g t r e e , T ( 0 ) , i s a t l e a s t 2 :
B y s u i t a b l y i n c r e a s i n g ¼ b , t h e r e e x i s t s a ¼ b = ± ¸ 0 , s u c h t h a t t h e r e i s a t l e a s t o n e o p t i m a l s p a n -
n i n g t r e e , T ( ± ) , w h e r e t h e d e g r e e o f v e r t e x b i s e x a c t l y e q u a l t o 2 ( R e f e r t o L e m m a 3 o f S h m o y s a n d
W i l l i a m s o n [ 2 3 ] ) . C o n s i d e r s u c h a n o p t i m a l t r e e a n d l e t p a n d q b e t h e t w o v e r t i c e s c o n n e c t e d t o
v e r t e x b i n t h e s a m e . L e t ¹ T = T ( ± ) S ( p ; q ) n f ( b ; p ) ; ( b ; q ) g d e n o t e t h e t r e e s p a n n i n g v e r t i c e s i n ¹ V .
B y d e ¯ n i t i o n ,
L D ( ¼ 0 ; V 0 ) = X ( i ; j ) 2 T ( ± )
( C i j + ¼ 0 i
+ ¼ 0 j
) ¡ 2 X i 2 V 0
¼ 0 i
= C p b + C q b + ¼ ¤ p + ¼ ¤ q + 2 ± + X ( i ; j ) 2 T ( ± ) n f ( b ; p ) ; ( b ; q ) g
( C i j + ¼ ¤ i + ¼ ¤ j )
¡ 2 X i 2 ¹ V
¼ ¤ i ¡ 2 ± :
( 3 5 )
S i n c e t h e c o s t s s a t i s f y t h e t r i a n g l e i n e q u a l i t y , C p b + C q b ¸ C p q . T h e r e f o r e ,
1 1
L D ( ¼ 0 ; V 0 ) ¸ C p q + ¼ ¤ p + ¼ ¤ q + X ( i ; j ) 2 T ( ± ) n f ( b ; p ) ; ( b ; q ) g
( C i j + ¼ ¤ i + ¼ ¤ j ) ¡ 2 X i 2 ¹ V
¼ ¤ i
= X ( i ; j ) 2 ¹ T
( C i j + ¼ ¤ i + ¼ ¤ j ) ¡ 2 X i 2 ¹ V
¼ ¤ i
¸ m a x
¼ ¸ 0
L D ( ¼ ; ¹ V ) :
( 3 6 )
I n t h e a b o v e a r g u m e n t w e h a v e s h o w n t h a t t h e r e e x i s t s a ¼ b ¸ 0 w h e r e L D ( ¼ 0 ; V 0 ) ¸ m a x ¼ ¸ 0 L D ( ¼ ; ¹ V ) .
H e n c e t h e a s s u m p t i o n m u s t b e f a l s e . T h e r e f o r e m a x ¼ ¸ 0 L D ( ¼ ; ¹ V ) · m a x ¼ 0 ¸ 0 L D ( ¼ 0 ; V 0 ) .
P r o p o s i t i o n I V . 4 : S u p p o s e ¹ V µ V 0 a n d j ¹ V j i s o d d . L e t M b e t h e m i n i m u m c o s t m a t c h i n g o n ¹ V
w i t h c a r d i n a l i t y ¹ V ¡ 1
2 . I f t h e c o s t s s a t i s f y t h e t r i a n g l e i n e q u a l i t y , t h e n C ( M ) · 1
2 C H P P
V 0 .
P r o o f : F o l l o w s f r o m P r o p o s i t i o n s I V . 2 a n d I V . 3 .
P r o p o s i t i o n I V . 5 : ( B o u n d o n t h e c o s t o f m a t c h i n g ) S u p p o s e S i µ P i ( x ¤ ) a n d j S i j i s o d d . L e t M i
b e t h e m i n i m u m c o s t m a t c h i n g o n S i w i t h c a r d i n a l i t y S i ¡ 1
2 . I f t h e c o s t s s a t i s f y t h e t r i a n g l e i n e q u a l i t y ,
t h e n P i = 1 ; ¢ ¢ ¢ ; k C ( M i ) · 1
2 C o p t
V .
P r o o f : N o t e t h a t t h e H a m i l t o n i a n p a t h p r o b l e m c o n s i d e r e d i n e q u a t i o n s ( 2 4 - 2 8 ) d o e s n o t r e q u i r e
t h e p a t h t o s t a r t a t a n y d e p o t v e r t e x . E n f o r c i n g a c o n s t r a i n t t h a t t h a t t h e p a t h s h o u l d s t a r t a t t h e
d e p o t v e r t e x c a n o n l y i n c r e a s e t h e o p t i m a l L P r e l a x a t i o n c o s t . T h e r e f o r e , C H P P
P i ( x ¤ ) · C l p
P i ( x ¤ ) . T h e r e f o r e ,
X i = 1 ; ¢ ¢ ¢ ; k
C ( M i ) ·
1
2 X i = 1 ; ¢ ¢ ¢ ; k
C H P P
P i ( x ¤ ) ( f r o m P r o p o s i t i o n I V . 4 )
·
1
2 X i = 1 ; ¢ ¢ ¢ ; k
C l p
P i ( x ¤ )
·
1
2 X i = 1 ; ¢ ¢ ¢ ; k
m a x
¼ i ¸ 0
w ( ¼ i ; P i ( x ¤ ) ) ( f r o m P r o p o s i t i o n I I . 1 )
=
1
2
m a x
¼ ¸ 0
( ¼ ; V ) ( f r o m P r o p o s i t i o n I I . 3 )
·
1
2
C o p t
V : ( f r o m P r o p o s i t i o n I I . 1 ) ( 3 7 )
C o m b i n i n g P r o p o s i t i o n s I V . 5 a n d I V . 1 p r o v e s t h e o r e m I I I . 1 .
R e f e r e n c e s
[ 1 ] C e r d e i r a , J . O . , 1 9 9 4 . M a t r o i d s a n d a f o r e s t c o v e r p r o b l e m . M a t h e m a t i c a l P r o g r a m m i n g 6 6 , p . 4 0 3 - 4 0 5 .
[ 2 ] N . C h r i s t o ¯ d e s , W o r s t - c a s e a n a l y s i s o f a n e w h e u r i s t i c f o r t h e T r a v e l i n g S a l e s m a n P r o b l e m , T e c h n i c a l R e p o r t 3 8 8 , G r a d u a t e
S c h o o l o f I n d u s t r i a l A d m i n i s t r a t i o n , C a r n e g i e - M e l l o n U n i v e r s i t y , P i t t s b u r g h , P A , 1 9 7 6 .
[ 3 ] C o r d o n e , R . , M a ± o l i , F . , 2 0 0 4 . O n t h e c o m p l e x i t y o f g r a p h t r e e p a r t i t i o n p r o b l e m s . D i s c r e t e A p p l i e d M a t h e m a t i c s 1 3 4 ,
p . 5 1 - 6 5 .
[ 4 ] E d m o n d s , J . , 1 9 7 0 . S u b m o d u l a r f u n c t i o n s , m a t r o i d s , a n d c e r t a i n p o l y h e d r a , i n : C o m b i n a t o r i a l S t r u c t u r e s a n d T h e i r A p p l i c a -
t i o n s ( P r o c e e d i n g s C a l g a r y I n t e r n a t i o n a l C o n f e r e n c e o n C o m b i n a t o r i a l S t r u c t u r e s a n d T h e i r A p p l i c a t i o n s , C a l g a r y , A l b e r t a ,
J u n e 1 9 6 9 ; R . G u y , H . H a n a n i , N . S a u e r , J . S c h o n h e i m , e d s . ) , G o r d o n a n d B r e a c h , N e w Y o r k , p p . 6 9 8 7 .
[ 5 ] F i s h e r , M . , 1 9 8 1 . T h e L a g r a n g e a n r e l a x a t i o n m e t h o d f o r s o l v i n g i n t e g e r p r o g r a m m i n g p r o b l e m s , M a n a g e m e n t S c i e n c e 2 7 , 1 1 8 .
[ 6 ] H . N . G a b o w a n d R . E . T a r j a n , E ± c i e n t a l g o r i t h m s f o r a f a m i l y o f m a t r o i d i n t e r s e c t i o n p r o b l e m s , J . A l g o r i t h m s 5 ( 1 9 8 4 ) 8 0 - 1 3 1 .
1 2
[ 7 ] G u s ¯ e l d , M a t r c i d o p t i m i z a t i o n 4 t h t h e i n t e r l e a v i n g o f t w o o r d e r e d s e t s , D i s c r . A p p l . M a t h . 8 , 1 9 8 4 , p p 4 1 - 5 0 .
[ 8 ] M a r t i n G r o t s c h e l , L a s z l o L o v a s z a n d A l e x a n d e r S c h r i j v e r . T h e e l l i p s o i d m e t h o d a n d i t s c o n s e q u e n c e s i n c o m b i n a t o r i a l o p t i -
m i z a t i o n . C o m b i n a t o r i c a 1 ( 2 ) : 1 6 9 - 1 9 7 ( 1 9 8 1 )
[ 9 ] G u o X i n g , Y . , 1 9 9 5 . T r a n s f o r m a t i o n o f m u l t i d e p o t m u l t i s a l e s m e n p r o b l e m t o t h e s t a n d a r d t r a v e l i n g s a l e s m a n p r o b l e m . E u r o -
p e a n J o u r n a l o f O p e r a t i o n a l R e s e a r c h 8 1 , p . 5 5 7 - 5 6 0 .
[ 1 0 ] G u t t m a n n - B e c k , N . , H a s s i n , R . , K h u l l e r , S . , a n d R a g h a v a c h a r i , B , 2 0 0 0 . A p p r o x i m a t i o n A l g o r i t h m s w i t h B o u n d e d P e r f o r -
m a n c e G u a r a n t e e s f o r t h e C l u s t e r e d T r a v e l i n g S a l e s m a n P r o b l e m . 1 9 9 8 F S T & T C S C o n f e r e n c e ( M a d r a s , I n d i a ) . A l g o r i t h m i c a
V o l 2 8 p p . 4 2 2 { 4 3 7 , ( 2 0 0 0 ) .
[ 1 1 ] H e l d , M . , K a r p , R . M . , 1 9 7 0 . T h e t r a v e l i n g s a l e s m a n p r o b l e m a n d m i n i m u m s p a n n i n g t r e e s . O p e r a t i o n s R e s e a r c h 1 8 , p . 1 1 3 8 -
1 1 6 2 .
[ 1 2 ] H o o g e v e e n , J . A . , 1 9 9 1 . A n a l y s i s o f c h r i s t o ¯ d e s ' h e u r i s t i c : S o m e p a t h s a r e m o r e d i ± c u l t t h a n c y c l e s . O p e r a t i o n s R e s e a r c h
L e t t e r s , 1 0 : 2 9 1 { 2 9 5
[ 1 3 ] K a r a , I . , B e k t a s , T . , 2 0 0 5 . I n t e g e r p r o g r a m m i n g f o r m u l a t i o n s o f m u l t i p l e s a l e s m e n p r o b l e m s a n d i t s v a r i a t i o n s . E u r o p e a n
J o u r n a l o f O p e r a t i o n a l R e s e a r c h ( a v a i l a b l e c u r r e n t l y a t h t t p : / / w w w . c r t . u m o n t r e a l . c a / t o l g a / ) .
[ 1 4 ] L a w l e r , E . , D e c 1 9 7 5 . M a t h e m a t i c a l P r o g r a m m i n g , v o l 9 , N u m b e r 1 , p p 3 1 - 5 6 .
[ 1 5 ] N e m h a u s e r , G . L . , a n d W o l s e y , L . , 1 9 8 8 . I n t e g e r a n d C o m b i n a t o r i a l O p t i m i z a t i o n , J . W i l e y a n d S o n s .
[ 1 6 ] P a p a d i m i t r i o u , C . H . , S t e i g l i t z , K . , 1 9 9 8 . C o m b i n a t o r i a l O p t i m i z a t i o n : A l g o r i t h m s a n d C o m p l e x i t y , D o v e r P u b l i s h e r s .
[ 1 7 ] M . L a g o u d a k i s , V . M a r k a k i s , D . K e m p e , P . K e s k i n o c a k , S . K o e n i g , A . K l e y w e g t , C . T o v e y , A . M e y e r s o n a n d S . J a i n ,
2 0 0 5 . A u c t i o n - B a s e d M u l t i - R o b o t R o u t i n g . I n P r o c e e d i n g s o f t h e I n t e r n a t i o n a l C o n f e r e n c e o n R o b o t i c s : S c i e n c e a n d S y s t e m s
( R O B O T I C S ) , p p 3 4 3 - 3 5 0 .
[ 1 8 ] R a t h i n a m , S . , R . S e n g u p t a a n d S . D a r b h a , \ A R e s o u r c e A l l o c a t i o n A l g o r i t h m f o r M u l t i - V e h i c l e S y s t e m s w i t h N o n - h o l o n o m i c
C o n s t r a i n t s , " V o l . 4 , n o . 1 , p p . 9 8 - 1 0 4 , I E E E T r a n s a c t i o n s o n A u t o m a t i o n S c i e n c e s a n d E n g i n e e r i n g , J a n u a r y 2 0 0 7 .
[ 1 9 ] R a t h i n a m , S . a n d S e n g u p t a , R . , 2 0 0 6 . " L o w e r a n d U p p e r b o u n d s f o r a M u l t i p l e D e p o t U A V R o u t i n g P r o b l e m " , I E E E C o n t r o l
a n d D e c i s i o n C o n f e r e n c e , S a n D i e g o , C a l i f o r n i a .
[ 2 0 ] R a t h i n a m , S . a n d S e n g u p t a , R . \ 5
3 - A p p r o x i m a t i o n A l g o r i t h m f o r a M u l t i p l e D e p o t , T e r m i n a l H a m i l t o n i a n P a t h P r o b l e m " ,
S u b m i t t e d t o N e t w o r k s .
[ 2 1 ] M a l i k , W . , R a t h i n a m , S . a n d D a r b h a , S . , F e b 2 0 0 7 . " A n a p p r o x i m a t i o n a l g o r i t h m f o r a s y m m e t r i c G e n e r a l i z e d M u l t i p l e
D e p o t , M u l t i p l e T r a v e l l i n g S a l e s m a n P r o b l e m " , A c c e p t e d i n O p e r a t i o n s R e s e a r c h L e t t e r s .
[ 2 2 ] R a t h i n a m , S . , 2 0 0 7 . R o u t i n g a n d M o n i t o r i n g a l g o r i t h m s f o r U A V s , P h . D t h e s i s , U n i v e r s i t y o f C a l i f o r n i a , B e r k e l e y .
[ 2 3 ] S h m o y s , D . B . , W i l l i a m s o n , D . P . , S e p t e m b e r 1 9 9 0 . A n a l y z i n g t h e H e l d - K a r p T S P b o u n d : a m o n o t o n i c i t y p r o p e r t y w i t h
a p p l i c a t i o n . I n f o r m a t i o n P r o c e s s i n g L e t t e r s , V o l 3 5 , I s s u e 6 , P a g e s : 2 8 1 - 2 8 5 .
[ 2 4 ] W o l s e y , . L . A . 1 9 8 0 H e u r i s t i c a n a l y s i s , l i n e a r p r o g r a m m i n g a n d b r a n c h a n d b o u n d . M a t h . P r o g r a m m i n g 1 3 , 1 2 1 - 3 4 .
[ 2 5 ] P a p a d i m i t r i o u , C . H . , a n d S t e i g l i t z , K . , C o m b i n a t o r i a l o p t i m i z a t i o n : a l g o r i t h m s a n d c o m p l e x i t y , P r e n t i c e - H a l l 1 9 8 2 , D o v e r
p u b l i c a t i o n s 1 9 9 8 .
[ 2 6 ] F r a n k , A . , A w e i g h t e d m a t r o i d i n t e r s e c t i o n a l g o r i t h m . J o u r n a l o f A l g o r i t h m s 2 , p . 3 2 8 - 3 3 6 , 1 9 8 1 .
V . A p p e n d i x
L e m m a V . 1 : T h e o p t i m a l s o l u t i o n ( t ¤ ; ¼ ¤ ) t o t h e l i n e a r p r o g r a m f o r m u l a t e d i n ( 1 6 ) s a t i s ¯ e s t h e
f o l l o w i n g c o n s t r a i n t s :
0 · t ¤ · n C m a x a n d 0 · ¼ ¤ i · n C m a x 8 i 2 V :
P r o o f : T h e o p t i m a l c o s t o f t h e L a g r a n g i a n d u a l p r o b l e m i s a l w a y s u p p e r b o u n d e d b y t h e o p t i m a l
c o s t o f t h e G M D H P P . T h e r e f o r e , t ¤ · C o p t
V · n C m a x . A l s o s i n c e t h e c o s t o f a l l t h e e d g e s a r e p o s i t i v e ,
t ¤ ¸ 0 .
S i n c e k ¸ 2 , o n e c a n a l w a y s c h o o s e a c o n s t r a i n e d f o r e s t , x f , s u c h t h a t
² a l l d e p o t v e r t i c e s i n x f h a v e d e g r e e e q u a l t o 0 e x c e p t o n e d e p o t v e r t e x , s , t h a t h a s d e g r e e 1 , a n d
² a l l d e s t i n a t i o n v e r t i c e s i n x f h a v e d e g r e e e q u a l t o 2 e x c e p t o n e d e s t i n a t i o n v e r t e x , q , t h a t h a s d e g r e e
1 .
F o r s u c h a c o n s t r a i n e d f o r e s t , v i ( x f ; V ) = 0 ; 8 i 2 f s g S f k + 1 ; k + 2 ; ¢ ¢ ¢ ; n g n f q g a n d v i ( x f ; V ) =
¡ 1 ; 8 i 2 f q g S f 1 ; 2 ; ¢ ¢ ¢ ; k g n f s g . T h e r e f o r e w e h a v e , u s i n g e q u a t i o n ( 1 6 ) ,
t ¤ · C V ( x f ) ¡ X i 2 f 1 ; ¢ ¢ ¢ ; k g n f s g
¼ ¤ i ¡ ¼ ¤ q :
S i n c e t ¤ ¸ 0 , a n d C V ( x f ) · n C m a x ,
X i 2 f 1 ; ¢ ¢ ¢ ; k g n f s g
¼ ¤ i + ¼ ¤ q · C V ( x f ) ¡ t ¤ · n C m a x : ( 3 8 )
1 3
U s i n g t h e a b o v e e q u a t i o n , a n d b y s u i t a b l y c h o o s i n g t h e d e p o t v e r t e x s a n d d e s t i n a t i o n v e r t e x q , w e
c a n c o n c l u d e t h a t e a c h ¼ ¤ i c a n b e u p p e r b o u n d e d b y n C m a x .
L e m m a V . 2 : L e t t o = C m i n
n + k , ¼ o
i = C m i n
n + k 8 i 2 V a n d ½ 1 = C m i n
n + k . L e t t h e c e n t e r o f t h e b a l l b e
y 1 = ( t o ; ¼ o
1 ; ¢ ¢ ¢ ; ¼ o n + k ) . T h e n B ( y 1 ; ½ 1 ) µ P .
P r o o f : C o n s i d e r a n y t ; ¼ 2 B ( y 1 ; ½ 1 ) . T h e n 0 · t · 2 C m i n
n + k a n d 0 · ¼ i · 2 C m i n
n + k f o r a l l i 2 V .
A l s o , f o r a n y c o n s t r a i n e d f o r e s t x , v i ( x ; V ) ¸ ¡ 1 f o r a l l i 2 V . N o w c o n s i d e r t h e r i g h t h a n d s i d e o f
t h e c o n s t r a i n t s i n t h e d e ¯ n i t i o n o f P ( e q u a t i o n 1 7 ) :
C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ¸ C V ( x ) ¡ X i 2 V
¼ i
¸ n C m i n ¡ 2 C m i n :
S i n c e n ¸ 3 a n d k ¸ 2 ,
C V ( x ) + X i 2 V
¼ i v i ( x ; S ) ¸ C m i n
> 2 C m i n = 5
¸ t :
I f t ; ¼ 2 B ( y 1 ; ½ 1 ) , i t i s e a s y t o s e e t h a t 0 · t · n C m a x a n d 0 · ¼ i · n C m a x 8 i 2 V . H e n c e , i f t ; ¼
2 B ( y 1 ; ½ 1 ) t h e n t ; ¼ 2 P . T h i s p r o v e s t h e L e m m a .
P r o p o s i t i o n I I . 3 : L e t ( ¼ ¤ ; x ¤ ) s o l v e t h e L a g r a n g i a n d u a l p r o b l e m , m a x ¼ ¸ 0 w ( ¼ ; V ) , w h e r e
w ( ¼ ; V ) = m i n
x 2 F ( V ) ; x i s a n i n t e g e r
[ C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ] :
L e t P i ( x ¤ ) b e t h e s e t o f a l l v e r t i c e s p r e s e n t i n t h e i t h t r e e o f t h e o p t i m a l s o l u t i o n x ¤ . T h e n ,
m a x
¼ ¸ 0
w ( ¼ ; V ) = X m = 1 ; ¢ ¢ ¢ ; k
m a x
¼ m ¸ 0
w ( ¼ m ; P m ( x ¤ ) ) ;
w h e r e ¼ m r e p r e s e n t s ¼ j f o r a l l j 2 P m ( x ¤ ) .
P r o o f : F o r m = 1 ; ¢ ¢ ¢ ; k , l e t r m d e n o t e t h e d e p o t v e r t e x p r e s e n t i n P m ( x ¤ ) . W e d e ¯ n e t h e
f o l l o w i n g a d d i t i o n a l c o n s t r a i n t s o n x u s i n g P m ( x ¤ ) ; m = 1 ; : : ; k a s f o l l o w s :
x i j = 0 ; f o r a l l i 2 P m ( x ¤ ) ; f o r a l l j 2 P l ( x ¤ ) ;
f o r a l l m ; l = 1 ; ¢ ¢ ¢ ; k a n d m 6 = l ;
X j 2 U P m ( x ¤ )
x r m j · p ; m = 1 ; ¢ ¢ ¢ ; k ;
X i ; j 2 P m ( x ¤ ) ; i < j
x i j = j P m ( x ¤ ) j ¡ 1 ; m = 1 ; ¢ ¢ ¢ ; k ;
X i ; j 2 B ; i < j
x i j · j B j ¡ 1 ; f o r a l l B µ P m ( x ¤ ) ; m = 1 ; ¢ ¢ ¢ ; k ;
x i j 2 f 0 ; 1 g ; f o r a l l i ; j 2 P m ( x ¤ ) ; i < j ; m = 1 ; ¢ ¢ ¢ ; k : ( 3 9 )
1 4
L e t a l l t h e c o n s t r a i n t s i n ( 3 9 ) b e d e n o t e d b y A c x · B c . L e t F ¤ ( V ) = f x : x 2 F ( V ) a n d A c x · B c g .
A d d i n g t h e s e c o n s t r a i n t s b a s e d o n x ¤ t o t h e c o n s t r a i n t s p r e s e n t i n F ( V ) w i l l n o t c h a n g e t h e o p t i m a l
L a g r a n g i a n d u a l c o s t , m a x ¼ ¸ 0 w ( ¼ ; V ) . T h a t i s ,
m a x
¼ ¸ 0
w ( ¼ ; V ) = m a x
¼ ¸ 0
m i n
x 2 F ( V ) ; x i s a n i n t e g e r
[ C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ]
= m a x
¼ ¸ 0
m i n
x 2 F ¤ ( V ) ; x i s a n i n t e g e r
[ C V ( x ) + X i 2 V
¼ i v i ( x ; V ) ] :
( 4 0 )
W e n e x t d e c o m p o s e t h e o b j e c t i v e f u n c t i o n a n d t h e s e t o f f e a s i b l e s o l u t i o n s . I f x 2 F ¤ ( V ) , t h e n
x i j = 0 f o r a l l i 2 P m ( x ¤ ) ; j 2 P l ( x ¤ ) ; m ; l 2 f 1 ; ¢ ¢ ¢ ; k g ; m 6 = l . T h e r e f o r e , e q u a t i o n ( 4 0 ) c a n b e w r i t t e n
a s
m a x
¼ ¸ 0
w ( ¼ ; V ) = m a x
¼ ¸ 0
m i n
x 2 F ¤ ( V ) ; x i s a n i n t e g e r X m = 1 ; ¢ ¢ ¢ ; k
[ C P m ( x ¤ ) ( x ) + X i 2 P m ( x ¤ )
¼ i v i ( x ; P m ( x ¤ ) ) ] :
( 4 1 )
L e t F 1 £ F 2 d e n o t e t h e c a r t e s i a n p r o d u c t o f t w o s e t s F 1 a n d F 2 . T h e n , x 2 F ¤ ( V ) i f a n d o n l y i f
( x 1 ; x 2 ; ¢ ¢ ¢ ; x k ) 2 £ k
m = 1 F ( P m ( x ¤ ) ) w h e r e e a c h x m r e p r e s e n t s a l l x i j f o r i ; j 2 P m ( x ¤ ) ; i < j . A l s o l e t
G m ( x m ; ¼ m ) = C P m ( x ¤ ) ( x ) + X i 2 P m ( x ¤ )
¼ i v i ( x ; P m ( x ¤ ) ) :
H e n c e , e q u a t i o n ( 4 1 ) c a n b e f u r t h e r s i m p l i ¯ e d a s f o l l o w s :
m a x
¼ ¸ 0
w ( ¼ ; V ) = m a x
¼ ¸ 0
m i n
( x 1 ; ¢ ¢ ¢ ; x k ) 2 £ k
m = 1 F ( P m ( x ¤ ) ) ; x m i s a n i n t e g e r X m = 1 ; ¢ ¢ ¢ ; k
G m ( x m ; ¼ m ) :
T h i s b r e a k s t h e i n n e r m i n i m i z a t i o n i n t o k i n d e p e n d e n t m i n i m i z a t i o n p r o b l e m s i m p l y i n g
m a x
¼ ¸ 0
w ( ¼ ; V ) = m a x
¼ ¸ 0 X m = 1 ; ¢ ¢ ¢ ; k
m i n
x m 2 F ( P m ( x ¤ ) ) ; x m i s a n i n t e g e r
G m ( x m ; ¼ m ) :
A p p l y i n g t h e s a m e r e a s o n i n g t o t h e m a x i m i z a t i o n p r o b l e m w e g e t
m a x
¼ ¸ 0
w ( ¼ ; V ) = X m = 1 ; ¢ ¢ ¢ ; k
m a x
¼ m ¸ 0
m i n
x m 2 F ( P m ( x ¤ ) ) ; x m i s a n i n t e g e r
G m ( x m ; ¼ m )
= X m = 1 ; ¢ ¢ ¢ ; k
m a x
¼ m ¸ 0
w ( ¼ m ; P m ( x ¤ ) ) :