On patching algorithms for random asymmetric travelling salesman problems |
| |
Authors: | M. E. Dyer A. M. Frieze |
| |
Affiliation: | (1) Leeds University, Leeds, England;(2) Carnegie-Mellon University, 15213-3890 Pittsburgh, PA, USA |
| |
Abstract: | Let the arc-lengthsLij of a complete digraph onn vertices be independent uniform [0, 1] random variables. We consider the patching algorithm of Karp and Steele for the travelling salesman problem on such a digraph and give modifications which tighten the expected error. We extend these ideas to thek-person travelling salesman problem and also consider the case where cities can be visited more than once. |
| |
Keywords: | Travelling salesman problem probabilistic analysis heuristics |
本文献已被 SpringerLink 等数据库收录! |
|