Non-Abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem
Sven Oliver Krumke, Luigi Laura, Maarten Lipmann, Alberto Marchetti-Spaccamela, Willem E. de Paepe, Diana Poensgen, Leen Stougie, Jansen, K., Leonardi, S., Vazirani, V. · TU/e Research Portal · 2002
In the online traveling salesman problem (OlTsp) requests for visits to cities arrive online while the salesman is traveling. We study the Fmax-OlTsp where the objective is to minimize the maximum flow time. This objective is particularly interesting for applications. Unfortu-nately, there can be no competitive algorithm, neither deterministic nor randomized. Hence, competitive analysis fails to distinguish online algo-rithms. 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 Fmax-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 non-abusive adversary.