Average-case approximation ratio of the 2-opt algorithm for the TSP |
| |
| Authors: | Christian Engels |
| |
| Institution: | Saarland University, Department of Computer Science, Postfach 151150, 66041 Saarbrücken, Germany |
| |
| Abstract: | We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly  for instances with n nodes, where the edge weights are drawn uniformly and independently at random. |
| |
| Keywords: | Traveling salesman problem 2-opt Average-case analysis Approximation ratio |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
