The Maximum Hamilton Path Problem with Parameterized Triangle Inequality

Weidong Li, Jianping Li, Zefeng Qiao, Honglin Ding

Yunnan University, Kunming, PR China.

DOI: 10.4236/cn.2013.51B022                

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

Conflicts of Interest

The authors declare no conflicts of interest.

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