Back
 CN  Vol.5 No.1 B , February 2013
The Maximum Hamilton Path Problem with Parameterized Triangle Inequality
Abstract: Given a complete graph with edge-weights satisfying parameterized triangle inequality, we consider the maximum Hamilton path problem and design some approximation algorithms.
Cite this paper: Li, W. , Li, J. , Qiao, Z. and Ding, H. (2013) The Maximum Hamilton Path Problem with Parameterized Triangle Inequality. Communications and Network, 5, 96-100. doi: 10.4236/cn.2013.51B022.
References

[1]   Z.-Z. Chen and T. Nagoya, “Improved Approximation Algorithms for Metric Max TSP,” Journal of Combinatorial Optimization, Vol. 13, No. 4, 2007, pp. 321-336. doi:10.1007/s10878-006-9023-7

[2]   Z.-Z. Chen, Y. Oka-moto and L. Wang, “Improved Deterministic 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 Algorithm Formetric Max TSP,” Information Processing Letters, 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 Algorithms 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,” Theoretical 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 Operational Research, 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 approximation 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 Maximum TSP,” Theoretical Computer Science, Vol. 411, No. 26-28, 2010, pp. 2537-2541. doi:10.1016/j.tcs.2010.03.012

 
 
Top