Research ArticleOpen AccessGoogle Scholar indexed
The Maximum Hamilton Path Problem with Parameterized Triangle Inequality
Yunnan University, Kunming, PR China
Yunnan University, Kunming, PR China
Yunnan University, Kunming, PR China
Yunnan University, Kunming, PR China
- 1 Yunnan University, Kunming, PR China
- 2 Yunnan University, Kunming, PR China
- 3 Yunnan University, Kunming, PR China
- 4 Yunnan University, Kunming, PR China
Communications and Network·Volume 05 (2013)·Pages 96–100·Published 28 February 2013·DOI10.4236/cn.2013.51B022
Copy link · social · email
Abstract
Given a complete graph with edge-weights satisfying parameterized triangle inequality, we consider the maximum Hamilton path problem and design some approximation algorithms.
KeywordsMaximum Traveling Salesman ProblemParameterized Triangle InequalityApproximation Algorithm
- 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
- 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
- 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 Algorithm Formetric Max TSP,” Information Processing Letters, 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 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.
- 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,” Theoretical 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 Operational Research, Vol. 161, 2005, pp. 721-735. doi:10.1016/j.ejor.2003.09.007
- 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
- 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