Share This Article:

The Maximum Hamilton Path Problem with Parameterized Triangle Inequality

Abstract Full-Text HTML Download Download as PDF (Size:84KB) PP. 96-100
DOI: 10.4236/cn.2013.51B022    2,415 Downloads   3,327 Views  

ABSTRACT

Given a complete graph with edge-weights satisfying parameterized triangle inequality, we consider the maximum Hamilton path problem and design some approximation algorithms.

Conflicts of Interest

The authors declare no conflicts of interest.

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

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.