Name
Abstract | ||
|---|---|---|
We consider eight heuristics for constructing approximate solutions to the traveling salesman problem and analyze their complexity in a model of parallel computation. The problems of finding a tour by the nearest neighbor, nearest merger, nearest insertion, cheapest insertion, and farthest insertion heuristics are shown to be P-complete. Hence, it is unlikely that such tours can be obtained in polylogarithmic work space on a sequential computer or in polylogarithmic time on a computer with unbounded parallelism. The double minimum spanning tree and nearest addition heuristics can be implemented to run in polylogarithmic time on a polynomial number of processors. For the Christofides heuristic, we give a randomized polylogarithmic approximation scheme requiring a polynomial number of processors. |
Year | DOI | Venue |
|---|---|---|
1989 | 10.1016/0196-6774(89)90015-1 | J. Algorithms |
Field | DocType | Volume |
k-nearest neighbors algorithm,Discrete mathematics,Combinatorics,Heuristic,Polynomial,Parallel processing,Algorithm,Heuristics,Travelling salesman problem,Parallel complexity,Mathematics,Minimum spanning tree | Journal | 10 |
Issue | ISSN | Citations |
2 | 0196-6774 | 9 |
PageRank | References | Authors |
1.44 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gerard A. P. Kindervater | 1 | 21 | 2.86 |
| J. K. Lenstra | 2 | 1689 | 329.39 |
| David B. Shmoys | 3 | 4829 | 601.03 |