Name
Abstract | ||
|---|---|---|
We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly O(n) for instances with n nodes, where the edge weights are drawn uniformly and independently at random. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.orl.2008.12.002 | Oper. Res. Lett. |
Keywords | Field | DocType |
average-case analysis,n node,salesman problem,average-case approximation ratio,2-opt,approxima- tion ratio,2-opt heuristic,2-opt algorithm,edge weight,expected approximation ratio,approximation ratio,traveling salesman problem,2 opt | Combinatorics,Heuristic,Mathematical optimization,Algorithm,Travelling salesman problem,2-opt,Mathematics | Journal |
Volume | Issue | ISSN |
37 | 2 | Operations Research Letters |
Citations | PageRank | References |
8 | 0.52 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christian Engels | 1 | 10 | 3.95 |
| Bodo Manthey | 2 | 63 | 5.38 |