 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 Email: *jianping@ynu.edu.cn 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 . 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()OnOP OPT'()wE'ET'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. TWhen 1, Monnot  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. 22/3In this paper, we first present a deterministic approxi- Mation algorithm with performance ratio 41162n For the MHP without specified endpoint, and a random- Ized algorithm with expected ratio 313124On by Modifying the algorithm in , where n is the number of vertices in G. We also present a determinant approxima- tion algorithm with performance ratio 416 for the MHP with one specified end point, which improves the result in . 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  introduced the MTSP with -parameterized trian-gle inequality for 1[,1)2, motivated by the minimum traveling salesman problem with -parameterized triangle inequality in . 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 iC*Corresponding author. Copyright © 2013 SciRes. CN W. D. LI ET AL. 97Hamiltonian cycle. They  proved that the perform- ance ratio of their algorithm is 12KK , where min|1,2,,iKCi l. Since 3iC for the cycle cover of undirected graph, the ratio is at least 13. 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 , where two approximation algorithms are given. In 1984, Serdyukov presented (in Russian) an elegant 34- approximation algorithm. Afterwards, Has sin and Rubinstein  presented a randomized algorithm whose expected approximation ratio is at least 25 133 32, where  is an arbitrarily small constant. Chen, Oka-moto, and Wang  first gave a deterministic approxi-mation algorithm with the ratio better than 34, which is a 6181- approximation and a nontrivial derandomization of the algorithm from . Very recently, Paluch, Mucha, and Madry  first presented a fast deterministic 79-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  first designed a 56-approximation algorithm for the metric maximum TSP. Hassin and Rubinstein designed a randomized approximation al-gorithm for themetric maximum TSP whose expected approximation ratio is 3718On, where n is the num- ber of vertices in the graph. This algorith m had later been derandomized by Chen and Nagoya , at a cost of a slightly worse approximation factor of 3718On. Very recently, Kowalik and Mucha  extended the ap-proach of processing local configuration susing so-called loose-ends in , and presented a deterministic 78-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 , Hassin and Rubinstein gave a randomized algo-rithm the maximum TSP . We modify it to the MHP problem. Algorithm A0: 1. Compute a maximum cycle cover 12,,. . .,lCC C. Without loss of generality, we assume that satisfies 1C11iiwCwCCC for any 1,2,. . .,1il. 2. Delete from each cycle a random edge. Let and be the ends of the path that results from . iuiCiviP3. Give each path a random orientation and form a Hamilton path HPiP by adding connecting edges be-tween the head of and thetail of , 1iP1,2,. . .,1il. Theorem 1. For any 12, the expected approxima- Tion ratio of Algorithm A0 for the MHP problem is 41162OPTn. Proof. Clearly,    1111111111111111,,4 ,,11 ,,2211 1,,2211 112lliiiiiiiii iilliiiiilliiiiiwTwPwu uwu vwvu wvvwPwuv wuvwCwu vwu vK    1()2411 .62wnOPTn Here, the first inequality follows from the -param- eterized triangle inequality, the second in equality follows from the assumption that satisfies 1C11iiwCwCCC, and the last inequality follows from. This com- 3KCopyright © 2013 SciRes. CN 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-bo2Based on Serdyukov’s algorithm in  and the randomization version of Kostochka & Serdyukov’s algo-rithm, Hassin and Rubinstein  presented a new algo-rithm for the maximum TSP problem. We modify it to the MHP problem. Algorithm B0: 1) Compute a m12,,. . .,lCC C of G. ximum-2) Compute a ma3) For 2,. . .,is, identify ,iefE C such tth {}Me and {}Mf ar Randomly choos , }e subtours.e {ge{}g and f (eh probability 1/2 ). Set iiPC {}ach witMMg. e PT4) Completl 1iirithminto a tour as in Kost1odochka & Se d nes of paths in M. Crdyukov’s algo . 5) Let Sbethe set of enompute a perfect matching Srandom M over S. Delete an edge from each cycle in SMMrbitrarily com-plete S. AMM into a tour 2T6) Lhe maximumw. - eightet T be ted tour betweenan 1T d 2T and e be the lightest edge in T, output the Ham-ilton path {}HPT e . Theorem 2.n For ay 1[, )2 , the expected w by the Height of the tour T returnedassin & Rubin-stein’s algorithm for the maximum TSP with -pa- rameterized triangle inequality satisfies 1312.4wTO OPTn Proof. Denote by  di the relative weight in C of the ], we obtainedges 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  '141211222 4wT wOPT Also, we have .141122 4SSwM'12 12 ,4OPT and '2312 1211.4wTO OPTn  Thus,  1212 '3wmaxw,w13ww 12 .24TTTTT OOPnT As e is the lightest edge in T, we have  '33 11w13112 141312. 4 wHP TnOOPnnOOPTn  T1 Based on the idea of Chen et al.  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  derandomize Hassin & Rubin-stein’s algorithm mat a cost of a slightly worse approxi-mation factor of n371.8 Similarly to , we obtain the following theorem. OnTheorem 3. For any 12, there is a deterministic Alg orit hm for the maximu m TSP with -parameterized triangle inequality with approximation ratio of 313124On. 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 wwM Mwedge,sr for{}V s each r. We find 1n feasible solutions and output the best one. The detailed algo-Copyright © 2013 SciRes. CN W. D. LI ET AL. 99rithms are presents as follows. Algorithm A1: 1) For each compute a maximum cycle cover r containing the edge {}rV s ,12,,. . .,rr lCCCrr,sr. Assume that contains 1rC,sr and ,0wsr. 2) Delete a minimum weight edge from each cycle , for , and the edge riC2,. . .,ril,sriP from 1. Let and iv bethe ends of the path that results from , where and vr. rCiuiC1us2l13) If , construct two Hamilton paths as follows: r1122221222:,:.HPsPruPvHPsPrvPu If , construct four Hamilton paths as follows. 3rl1122233321222333:,:.rrrrrrllllllHPsPruPvuPv uPvHPsPrvPuvPuvPu When l is odd, 3122233341222333::.rrrrrrllllll,HPsPrvPuuPv uPvHPsPruPvvPu vPu When l is even, 3122233341222333:,:rrrrrrllllll.HPsPrvPuuPv vPuHPsPruPvvPu uPv 4) Compute a maximum-weighted Hamilton path rHP2rl in where , if . |1,2,3,4iHPi 34HP HP5. Output a maximum-weighted Hamilton path HP in |rHPr Vs . Lemma 4. For each , the objective value rV sof rHP is at least 416rw. Proof. If , we have 2rl    1212 212 222222 22, ,122,122,12241 .3rrrrrwHP wHPwPwP wruwrvwPwPwu vwwuvwCwCw2 Thus,  1241 .26rwP wPwHP wIf , we have 3rlr   412211111212242,2, ,,,,24,244,rrrrriiliiliiii ii iiilliiiiilriiiwHPwP wruwrvwuuwuvwvuwvvwP wuvwwuv1 82 ,3rw where the second inequality follows from 12, and the last inequality follows from and 3KwOPT. Therefore, 41141.46rriiwHP wHPw This completes the proof. Theorem 5. The weight of the Hamilton path HP is at least 416 OPT. Proof. Since HP is the maximum-weighted Hamilton pathin |rHPr Vs , we have max41 max641 ,6rrVsrrVswHPwHPwOPT where the second inequality follows from Lemma 4, and thelast inequality follows from the fact {}max rrVs w  isan obvious upper bound on . OPT4. 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 Copyright © 2013 SciRes. CN W. D. LI ET AL. Copyright © 2013 SciRes. CN 100 Foundation of C hi na [N o. 11 12 6 31 5] . REFERENCES  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  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  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  D. Hartvigsen, “Extensions of Matching Theory,” Ph.D. Thesis, Carnegie-Mellon University, Pittsburgh, PA, 1984.  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  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  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.  L. Kowalik and M. Mucha, “35/44-approximation for Asymmetric Maximum TSP with Triangle Inequality,” Algorithmica, doi:10.1007/s00453-009-9306-3  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  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  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  A. I. Serdyukov, “The Traveling Salesman Problem of the Maximum (in Russian),” UpravlyaemyeSistemy, Vol. 25, 1984, pp. 80-86.  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  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