TY - GEN A1 - Krumke, Sven A1 - Laura, Luigi A1 - Lipmann, Maarten A1 - Marchetti-Spaccamela, Alberto A1 - Paepe, Willem de A1 - Poensgen, Diana A1 - Stougie, Leen T1 - Non-Abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling Salesman Problem N2 - 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 \emph{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. T3 - ZIB-Report - 02-36 KW - Online Algorithms KW - Competitive Analysis KW - Comparative Analysis Y1 - 2002 UR - https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/703 UR - https://nbn-resolving.org/urn:nbn:de:0297-zib-7038 ER -