Algorithms for the on-line travelling salesman

Citation
G. Ausiello et al., Algorithms for the on-line travelling salesman, ALGORITHMIC, 29(4), 2001, pp. 560-581
Citations number
21
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Engineering Mathematics
Journal title
ALGORITHMICA
ISSN journal
0178-4617 → ACNP
Volume
29
Issue
4
Year of publication
2001
Pages
560 - 581
Database
ISI
SICI code
0178-4617(200104)29:4<560:AFTOTS>2.0.ZU;2-8
Abstract
In this paper the problem of efficiently serving a sequence of requests pre sented in an on-line fashion located at points of a metric space is conside red. We call this problem the On-Line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We consider two versions of the problem. In the first one the server is not required to return to the departure point after all presented requests hav e been served. For this problem we derive a lower bound on the competitive ratio of 2 on the real line. Besides, a 2.5-competitive algorithm for a wid e class of metric spaces, and a 7/3-competitive algorithm for the real line are provided. For the other version of the problem, in which returning to the departure p oint is required, we present an optimal 2-competitive algorithm for the abo ve-mentioned general class of metric spaces. If in this case the metric spa ce is the real line we present a 1.75-competitive algorithm that compares w ith a approximate to1.64 lower bound.