Communications and Network, 2013, 5, 96-100
doi:10.4236/cn.2013.51B022 Published Online February 2013 (http://www.scirp.org/journal/cn)
The Maximum Hamilton Path Problem with Parameterized
Triangle Inequality
Weidong Li, Jianping Li*, Zefeng Qiao, Honglin Ding
1Department of Atmospheric Science, Yunnan University, Kunming, PR China
2Department of Mathematics, Yunnan University, Kunming, PR China
Received 2012
ABSTRACT
Given a complete graph with edge-weights satisfying parameterized triangle inequality, we consider the maximum-
Hamilton path problem and design some approximation algorithms.
Keywords: Maximum Traveling Salesman Problem; Parameterized Triangle Inequality; Approximation Algorithm
1. Introduction
Routing design problems are of a major importance in-
computer communications and combinatorial optimiza-
tion. The traveling salesman problem (TSP) and related
Hamilton path problem play important role in routing
design problems. Recently, some novel approximation
algorithms and randomized algorithms are designed for
these problems.
Let bea complete graph in which the
edge weights satisfy

,,GVEw

()(() ())wuvwux wxv

 
V for all
distinct nodes , the maximum Hamilton path
problem(MHP) with
,,uxv

-parameterized triangle inequal-
ity is to find a path with maximum weight that visits each
node exactly once.
A cycle cover is a subgraph in which each vertex in V
has a degree of exactly 2. A maximum cycle cover is one
with maximum total edge weight which can be computed
in time [4]. It is well-known that the weight of
the maximum cycle cover is an upper bound on ,
where denotes the weight of an optimal Hamilton
path (or tour). All the algorithms mentioned in this paper
start by constructing a maximum-weight cycle cover. A
subtour in this paper is a subgraph with no
non-Hamiltonian cycles or vertices of degree greater than
2. Thus by adding edges to a subtour it can be completed
to a tour. In this paper, for asubset ,
denotes the (expected) total weight of the edges in .
3
()On
OP OPT
'
()wE
'
E
T
'
EE
We call that an algorithm is a

-approximation algo-
rithm for the MHP if it always produces a feasible solu-
tion with objective at least OPT

, where OP de-
notes the optimal value. T
When 1

, Monnot [10] presented a 1/ -ap-
proximation algorithm for the MHP with two specified
endpoints and a -approximation algorithm for the
MHP with one specified end point. To the best of
knowledge, this is the unique result about MHP.
2
2/3
In this paper, we first present a deterministic approxi-
Mation algorithm with performance ratio 411
62n




For the MHP without specified endpoint, and a random-
Ized algorithm with expected ratio 3
1
31
2
4On







by
Modifying the algorithm in [7], where n is the number of
vertices in G. We also present a determinant approxima-
tion algorithm with performance ratio 41
6


 for the
MHP
with one specified end point, which improves the result
in [10].
A closely related problem is the maximum traveling
salesman problem (MTSP) with

-parameterized trian-
gleine quality which is to find a tour with maximum
weight that visits each node exactly once in a complete
graph in which the edge weights satisfy

-parameterized triangle in equality. Zhang, Yin, and Li
[14] introduced the MTSP with

-parameterized trian-
gle inequality for
1
[,1)
2
 , motivated by the minimum traveling salesman
problem with

-parameterized triangle inequality in
[13]. They firstcompute a maximum-weight cycle cover
1l
{,,. . .,C}C

, and then delete the minimum-weight
of the edges in and extend the remained paths to a
i
C
*Corresponding author.

W. D. LI ET AL. 97
Hamiltonian cycle. They [14] proved that the perform-
ance ratio of their algorithm is 12K
K



 , where

min|1,2,,
i
K
Ci l
. Since 3
i
C for the cycle
cover of undirected graph, the ratio is at least 1
3



.
Notice that the MTSP wit

h -parameterized trian-
gle inequality is a special case of the maximum TSP
which is first considered by Fisher, Nemhauser and
Wolsey [3], where two approximation algorithms are
given. In 1984, Serdyukov[12] presented (in Russian) an
elegant 3
4- approximation algorithm. Afterwards, Has
sin and Rubinstein [6] presented a randomized algorithm
whose expected approximation ratio is at least


25 1
33 32



,
where

is an arbitrarily small constant. Chen, Oka-
moto, and Wang [2] first gave a deterministic approxi-
mation algorithm with the ratio better than 3
4, which is a
61
81- approximation and a nontrivial derandomization of
the algorithm from [6]. Very recently, Paluch, Mucha,
and Madry [11] first presented a fast deterministic
7
9-approximation algorithm for the maximum TSP,
which isthe currently best result.
If 1

, the MTSP with

-parameterized triangle in
equality is exactly the metric maximum TSP. Kostochka
and Serdyukov [7] first designed a 5
6-approximation
algorithm for the metric maximum TSP. Hassin and
Rubinstein [5]designed a randomized approximation al-
gorithm for themetric maximum TSP whose expected
approximation ratio is 3
71
8On




, where n is the num-
ber of vertices in the graph. This algorith m had later been
derandomized by Chen and Nagoya [1], at a cost of a
slightly worse approximation factor of 3
71
8On



.
Very recently, Kowalik and Mucha [9] extended the ap-
proach of processing local configuration susing so-called
loose-ends in [8], and presented a deterministic 7
8-ap-
proximation algorithm for the metric maximum TSP,
which is the currently best result.
The paper is divided into four sections. In Section 2,
we will present some algorithms for the MHP problem-
without specified endpoint. In Section 3, we will presen-
tan algorithms for the MHP problem with one specified
end point. The pap er is concluded in the last section.
2. The MHP Problem without Specified
Endpoint
2.1. Modified Randomized Kostochka & Ser-
dyukov’s Algorithm
In [5], Hassin and Rubinstein gave a randomized algo-
rithm the maximum TSP [7]. We modify it to the MHP
problem.
Algorithm A0:
1. Compute a maximum cycle cover


12
,,. . .,l CC C.
Without loss of generality, we assume that satisfies
1
C




1
1
i
i
wC wC
CC
 for any 1,2,. . .,1il.

2. Delete from each cycle a random edge. Let and
be the ends of the path that results from .
i
u
i
C
i
vi P
3. Give each path a random orientation and form a
Hamilton path
H
P
i
P by adding connecting edges be-
tween the head of and thetail of ,
1i
P
1,2,. . .,1il

.
Theorem 1. For any 1
2
 , the expected approxima-
Tion ratio of Algorithm A0 for the MHP problem is
411
62
OPT
n


 


.
Proof. Clearly,
  

 
  
  
1
11
11
11
11
11
11
11
1,,
4
,,
11
,,
22
11
1,,
22
11
11
2
ll
iiiii
ii
ii ii
ll
iii
ii
ll
iii
ii
wTwPwu uwu v
wvu wvv
wPwuv wuv
wCwu vwu v
K









 

 

 



 





1()
2
411
.
62
w
n
OPT
n















Here, the first inequality follows from the

-param-
eterized triangle inequality, the second in equality follows
from the assumption that satisfies
1
C



1
1
i
i
wC wC
CC
,
and the last inequality follows from. This com- 3K

W. D. LI ET AL.
98
pletes the proof. It is well-known that ove random-
ized version of Kostochka & Serdyukov’s algorithm can
easily be derandomized by the standard method of condi-
tional expectation.
the ab
.2. Modified Hassin & Rubinstein’s Algorithm
-
aximum-weight cycle cover
weight matching M in G. h at-
bo
2
Based on Serdyukov’s algorithm in [12] and the ran
domization version of Kostochka & Serdyukov’s algo-
rithm, Hassin and Rubinstein [5] presented a new algo-
rithm for the maximum TSP problem. We modify it to
the MHP problem.
Algorithm B0:
1) Compute a m

12
,,. . .,l CC C of G.
ximum-

2) Compute a ma
3) For 2,. . .,is, identify ,i
efE C such t
th {}
M
e and
{}
M
f
 ar Randomly
choos , }e subtours. e {
g
e
{}g and
f (eh probability 1/2 ). Set
ii
PC {}
ach wit
M
Mg.
e P
T
4) Completl
1i i
rithminto a tour as in Kost
1
od
ochka &
Se d nes of paths in M.
C
rdyukov’s algo [7].
5) Let Sbethe set of en
ompute a perfect matching S
random
M
over S. Delete
an edge from each cycle in S
M
M
rbitrarily com-
plete S
. A
M
M
 into a tour 2
T
6) Lhe maximumw
.
- eightet T be ted tour between
an 1
T
d 2 T and e be the lightest edge in T, output the Ham-
ilton path {}
H
PT e .
Theorem 2.n For ay 1 [, )
2


 , the expected
w by the Height of the tour T returnedassin & Rubin-
stein’s algorithm[5] for the maximum TSP with

-pa-
rameterized triangle inequality satisfies

1

31
2.
4
wTO OPT
n












Proof. Denote by

di the relative weight in C of the
], we obtain
edges that were candates for deletion. Let ' OPT de-
note the value of the maximum-weighted Hamycle.
Clearly, '
OPT OPT. Similarly to the proof of Theo-
rem 1 in [5
ilton c
  
'
1
412
1 

1
22
2 4
wT wOPT








Also, we have
.
 
 
1
4
11
22 4
S
S
wM

'
12 12
,
4OPT




and



'
23
12 121
1.
4
wTO OPT
n


 






Thus,








 
12
12 '
3
wmaxw,w
1
3
ww 1
2
.
24
TTT
TT OOP
n














T
As e is the lightest edge in T, we have
 
'
3
3
1
1w
1
3
11
2
14
1
31
2. 4
wHP T
n
OOP
nn
OOPT
n













 

 
 














T
1
Based on the idea of Chen et al. [2] and the properti-
esof a folklore partition of the edg es of a 2n-vertex co m-
plete undirected graph into 2 perfect matchings,
Chen and Nagoya [1] derandomize Hassin & Rubin-
stein’s algorithm mat a cost of a slightly worse approxi-
mation factor of
n
3
71 

.
8 Similarly to [1], we obtain
the following theorem.
On



Theorem 3. For any 1
2
 , there is a deterministic
Alg orit hm for the maximu m TSP with

-parameterized
triangle inequality with approximation ratio of
3
1
31
2
4On





.
3. The Mhp Problem with One Specified
Endpoint
Let i be the specified endpoint. The MHP problem with
one specified endpoint is to find a maximum- weighted
Hamilton path starting from s. Our algorithm is based on
computing cycle cover containing the special
w
wM Mw













edge


,
s
r for{}V s each r

. We find 1n feasible
solutions and output the best one. The detailed algo-

W. D. LI ET AL. 99
rithms are presents as follows.

Algorithm A1:
1) For each compute a maximum cycle
cover r containing the edge
{}rV s ,

12
,,. . .,
rr l
CCC
r r


,
s
r.
Assume that contains

1
r
C

,
s
r and

,0wsr

.
2) Delete a minimum weight edge from each cycle
, for , and the edge
r
i
C2,. . .,r il

,
s
r
i
P from 1. Let and i v bethe ends of the path that results from
, where and vr.
r
C
i
u
i
C1 us
2l1 3) If , construct two Hamilton paths as follows:

r
11222
21222
:,
:.
H
PsPruPv
H
PsPrvPu
If , construct four Hamilton paths as follows. 3
r
l
11222333
21222333
:,
:.
rrr
rrr
lll
lll
H
PsPruPvuPv uPv
H
PsPrvPuvPuvPu


When l is odd,
31222333
41222333
:
:.
rrr
rrr
lll
lll
,
H
PsPrvPuuPv uPv
H
PsPruPvvPu vPu


When l is even,
31222333
41222333
:,
:
rrr
rrr
lll
lll
.
H
PsPrvPuuPv vPu
H
PsPruPvvPu uPv


4) Compute a maximum-weighted Hamilton path
r
H
P2
r
l in where , if .

|1,2,3,4
i
HPi 34 HP HP
5. Output a maximum-weighted Hamilton path HP in


|
r
H
Pr Vs .
Lemma 4. For each , the objective value

rV s
of r
H
P is at least

41
6r
w


.
Proof. If , we have 2
r
l

 
 
 
 

12
12 2
12 22
22
2
2
22, ,
1
22,
1
22,
1
22
41 .
3
r
r
rr
r
wHP wHP
wPwP wruwrv
wPwPwu v
wwuv
wC
wC
w





















2
Thus,
 
12
41 .
26
r
wP wP
wHP w



 
If , we have 3
r
l
r



 
 
 
 
4
1
22
1
1
111
2
12
2
42,2,
,,,,
2
4,
2
44,
r
r
rr
r
i
i
l
i
i
l
iiii ii ii
i
ll
iii
ii
l
rii
i
wHP
wP wruwrv
wuuwuvwvuwvv
wP wuv
wwuv






















1


82 ,
3r
w




where the second inequality follows from 1
2
 , and
the last inequality follows from and 3K


wOPT . Therefore,
  
4
1
141
.
46
rr
i
i
wHP wHPw






This completes the proof.
Theorem 5. The weight of the Hamilton path HP is at
least 41
6
OPT


.
Proof. Since HP is the maximum-weighted Hamilton
pathin




|
r
H
Pr Vs , we have






max
41
max6
41
,
6
r
rVs
r
rVs
wHPwHP
w
OPT











where the second inequality follows from Lemma 4, and
thelast inequality follows from the fact


{}
max r
rVs w   isan obvious upper bound on . OPT
4. Conclusions
In this paper, we presented some approximation algo-
rithms for two variants of the maximum Hamilton path
problem with parameterized triangle inequality. It is in-
teresting to design some better approximation algorithms
for these problems.
5. Acknowledgements
The work is supported by the National Natural Science
Foundation of China [No. 61063011] and the Tianyuan
Fund for Mathematics of the National Natural Science

W. D. LI ET AL.
100
Foundation of C hi na [N o. 11 12 6 31 5] .
REFERENCES
[1] Z.-Z. Chen and T. Nagoya, “Improved Approximation
Algorithms for Metric Max TSP,” Journal of Combinato-
rial Optimization, Vol. 13, No. 4, 2007, pp. 321-336.
doi:10.1007/s10878-006-9023-7
[2] Z.-Z. Chen, Y. Okamoto and L. Wang, “Improved De-
terministic Approximation Algorithms for Max TSP,”
Information Processing Letters, Vol. 95, No. 2, 2005, pp.
333-342. doi:10.1016/j.ipl.2005.03.011
[3] M. L. Fisher, G. L. Nemhauser and L. A. Wolsey, “An
Analysis of Approximation for Finding a Maximum
Weight Hamiltonian Circuit,” Operations Research, Vol.
27, No. 4, 1979, pp. 799-809. doi:10.1287/opre.27.4.799
[4] D. Hartvigsen, “Extensions of Matching Theory,” Ph.D.
Thesis, Carnegie-Mellon University, Pittsburgh, PA,
1984.
[5] R. Hassin, S. Rubinstein, “A 7/8-approximation Algo-
rithm Formetric Max TSP,” Information Processing Let-
ters, Vol. 81, No. 5, 2002, pp. 247-251.
doi:10.1016/S0020-0190(01)00234-4
[6] R. Hassin and S. Rubinstein, “Better Approximations for
Max TSP. Information Processing Letters, Vol. 75, No. 4,
2000, pp. 181-186. doi:10.1016/S0020-0190(00)00097-1
[7] A. V. Kostochka and A. I. Serdyukov, “Polynomial Algo-
rithms with the Estimates 3/4 and 5/6 for the Traveling
Salesman Problem of the Maximum (in Russian),”
Upravlyaemye Sistemy, Vol. 26, 1985, pp. 55-59.
[8] L. Kowalik and M. Mucha, “35/44-approximation for
Asymmetric Maximum TSP with Triangle Inequality,”
Algorithmica, doi:10.1007/s00453-009-9306-3
[9] L. Kowalik and M. Mucha, “Deterministic
7/8-approximation for the Metric Maximum TSP,” Theo-
retical Computer Science, Vol. 410, No. 47-49, 2009, pp.
5000-5009.
doi:10.1016/j.tcs.2009.07.051
[10] J. Monnot, “The Maximum Hamiltonian Path Problem
with Specified Endpoint(s),” European Journal of Opera-
tional Resear ch, Vol. 161, 2005, pp. 721-735.
doi:10.1016/j.ejor.2003.09.007
[11] K. Paluch, M. Mucha and A. Madry, “A 7/9 approxima-
tion Algorithm for the Maximum Traveling Salesman
Problem,” Lecture Notes In Computer Science, Vol. 5687,
2009, pp. 298-311. doi:10.1007/978-3-642-03685-9_23
[12] A. I. Serdyukov, “The Traveling Salesman Problem of the
Maximum (in Russian),” UpravlyaemyeSistemy, Vol. 25,
1984, pp. 80-86.
[13] T. Zhang, W. Li and J. Li, “An Improved Approximation
Algorithm for the ATSP with Parameterized Triangle
Inequality,” Journal of Algorithms, Vol. 64, 2009, pp.
74-78. doi:10.1016/j.jalgor.2008.10.002
[14] T. Zhang, Y. Yin and J. Li, “An Improved Approximation
Algorithm for the Maxi mum TSP,” Theoretical Computer
Science, Vol. 411, No. 26-28, 2010, pp. 2537-2541.
doi:10.1016/j.tcs.2010.03.012