CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Two short notes on the on-line traveling salesman: handling times and lookahead

Peter Damaschke (Institutionen för datavetenskap, Algoritmer)
Theoretical Computer Science (0304-3975). Vol. 289 (2002), 1, p. 845-852.
[Artikel, refereegranskad vetenskaplig]

We study extensions of the on-line travelling salesman problem. Our results are: The optimal competitive ratio 2 for arbitrary metric spaces also holds in the case of nonzero handling times. The optimal competitive ratio 3/2 on the half-line cannot be improved by randomization, but there is a 4/3-competitive algorithm under the assumption that the server is notified when the last request has been released. This ratio is also optimal.

Nyckelord: on-line algorithms, traveling salesman, handling times, lookahead

Denna post skapades 2006-09-25. Senast ändrad 2015-02-11.
CPL Pubid: 1885


Läs direkt!

Länk till annan sajt (kan kräva inloggning)

Institutioner (Chalmers)

Institutionen för datavetenskap, Algoritmer (2002-2004)


Information Technology

Chalmers infrastruktur