Non-abusiveness Helps:An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman problem

S.O. Krumke, L. Laura, M. Lipmann, A. Marchetti Spaccamela, W.E. Paepe, de, D. Poensgen, L. Stougie

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

32 Citaten (Scopus)

Samenvatting

In the online traveling salesman problem OlTsp requests for visits to cities arrive online while the salesman is traveling. We study the F max-OlTsp where the objective is to minimize the maximum flow time. This objective is particularly interesting for applications. Unfortunately, there can be no competitive algorithm, neither deterministic nor randomized. Hence, competitive analysis fails to distinguish online algorithms. Not even resource augmentation which is helpful in scheduling works as a remedy. This unsatisfactory situation motivates the search for alternative analysis methods. We introduce a natural restriction on the adversary for the F max-OlTsp on the real line. A non-abusive adversary may only move in a direction if there are yet unserved requests on this side. Our main result is an algorithm which achieves a constant competitive ratio against the nonabusive adversary.
Originele taal-2Engels
TitelApproximation Algorithms for Combinatorial Optimization (Proceedings APPROX 2002, Rome Italy, September 17-21, 2002)
RedacteurenK. Jansen, S. Leonardi, V. Vazirani
Plaats van productieBerlin
UitgeverijSpringer
Pagina's200-214
ISBN van geprinte versie3-540-44186-7
DOI's
StatusGepubliceerd - 2002

Publicatie series

NaamLecture Notes in Computer Science
Volume2462
ISSN van geprinte versie0302-9743

Vingerafdruk

Duik in de onderzoeksthema's van 'Non-abusiveness Helps:An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman problem'. Samen vormen ze een unieke vingerafdruk.

Citeer dit