Guaranteed performance heuristics for the bottleneck travelling salesman problem |
| |
Authors: | RGary Parker Ronald L Rardin |
| |
Institution: | School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332, USA;School of Industrial Engineering, Purdue University, W. Lafayette, IN 47907, USA |
| |
Abstract: | We consider constant-performance, polynomial-time, nonexact algorithms for the minimax or bottleneck version of the Travelling Salesman Problem. It is first shown that no such algorithm can exist for problems with arbitrary costs unless P = NP. However, when costs are positive and satisfy the triangle inequality, we use results pertaining to the squares of biconnected graphs to produce a polynomial-time algorithm with worst-case bound 2 and show further that, unless P = NP, no polynomial alternative can improve on this value. |
| |
Keywords: | Graphs combinatorics traveling salesman heuristic |
本文献已被 ScienceDirect 等数据库收录! |
|