<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>703</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2002-10-18</completedDate>
    <publishedDate>2002-10-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Non-Abusiveness Helps: An O(1)-Competitive Algorithm for Minimizing the Maximum Flow Time in the Online Traveling&#13;
Salesman Problem</title>
    <abstract language="eng">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.</abstract>
    <identifier type="serial">02-36</identifier>
    <identifier type="opus3-id">704</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7038</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of the 5th Int. Workshop on Approximation Algorithms for Combinatorial Optimization. Springer 2002. LNCS, 2462, pp. 200-214</enrichment>
    <author>Sven Krumke</author>
    <author>Luigi Laura</author>
    <author>Maarten Lipmann</author>
    <author>Alberto Marchetti-Spaccamela</author>
    <author>Willem de Paepe</author>
    <author>Diana Poensgen</author>
    <author>Leen Stougie</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-36</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Competitive Analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Comparative Analysis</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C59">Approximation methods and heuristics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ONLINE-PLANNING">ONLINE-PLANNING</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/703/ZR-02-36.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/703/ZR-02-36.pdf</file>
  </doc>
</export-example>
