An Approximate Algorithm for Triangle TSP with a Four-Vertex-Three-Line Inequality

Yong Wang
Additional contact information
Yong Wang: School of Renewable Energy, North China Electric University, Beijing, China

International Journal of Applied Metaheuristic Computing (IJAMC), 2015, vol. 6, issue 1, 35-46

Abstract: Traveling salesman problem (TSP) is a classic combinatorial optimization problem. The time complexity of the exact algorithms is generally an exponential function of the scale of TSP. This work gives an approximate algorithm with a four-vertex-three-line inequality for the triangle TSP. The time complexity is O(n2) and it can generate an approximation less than 2 times of the optimal solution. The paper designs a simple algorithm with the inequality. The algorithm is compared with the double-nearest neighbor algorithm. The experimental results illustrate the algorithm find the better approximations than the double-nearest neighbor algorithm for most TSP instances.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijamc.2015010103 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jamc00:v:6:y:2015:i:1:p:35-46

Access Statistics for this article

International Journal of Applied Metaheuristic Computing (IJAMC) is currently edited by Peng-Yeng Yin

More articles in International Journal of Applied Metaheuristic Computing (IJAMC) from IGI Global
Bibliographic data for series maintained by Journal Editor ().