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 [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. Copyright © 2013 SciRes. CN
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 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 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 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- 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 {} e and {} f ar Randomly choos , }e subtours. e { e {}g and f (eh probability 1/2 ). Set ii PC {} ach wit 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 over S. Delete an edge from each cycle in S M rbitrarily com- plete S . A 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 {} 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 , r 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. 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 , r. Assume that contains 1 r C , r and ,0wsr . 2) Delete a minimum weight edge from each cycle , for , and the edge r i C2,. . .,r il , 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 2l1 3) If , construct two Hamilton paths as follows: r 11222 21222 :, :. PsPruPv PsPrvPu If , construct four Hamilton paths as follows. 3 r l 11222333 21222333 :, :. rrr rrr lll lll PsPruPvuPv uPv PsPrvPuvPuvPu When l is odd, 31222333 41222333 : :. rrr rrr lll lll , PsPrvPuuPv uPv PsPruPvvPu vPu When l is even, 31222333 41222333 :, : rrr rrr lll lll . PsPrvPuuPv vPu PsPruPvvPu uPv 4) Compute a maximum-weighted Hamilton path r 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 Pr Vs . Lemma 4. For each , the objective value rV s of r 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 wOPT . 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 Pr Vs , we have max 41 max6 41 , 6 r rVs r rVs wHPwHP 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 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 [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
|