Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem |
| |
| Affiliation: | 1. Florey Institute of Neuroscience and Mental Health, University of Melbourne, Australia;2. Division of Clinical Neurosciences, University of Edinburgh, UK;1. Department of Communication Sciences and Disorders, Syracuse University, Syracuse, NY, USA;2. Syracuse University Libraries, Syracuse University, Syracuse, NY, USA;3. Shirley Ryan Affective and Emotion Rehabilitation Lab, Shirley Ryan AbilityLab, Chicago, IL, USA;4. Physical Medicine and Rehabilitation, Feinberg School of Medicine, Northwestern University, Chicago, IL, USA;1. Department of Internal Medicine, Dali Jen-Ai Hospital, Taichung, Taiwan, ROC;2. Department of Nursing, Central Taiwan University of Science and Technology, Taichung, Taiwan, ROC;3. College of Nursing, Central Taiwan University of Science and Technology, NO.666, Buzih Rd., Beitun District, Taichung 40601, Taiwan, ROC |
| |
| Abstract: | The purpose of this paper is to present heuristics for the bottleneck wandering salesperson problem and the bottleneck vehicle routing problem with the triangle inequality that are guaranteed to produce solutions that have a cost no more than twice the optimum. These heuristics are all best possible in the sense that the existence of a heuristic that guarantees a better ratio would imply that PP = NP, and this is widely believed to be false. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
