<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>396</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1999-03-12</completedDate>
    <publishedDate>1999-03-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online Dial-a-Ride Problem under Reasonable Load</title>
    <abstract language="eng">In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.</abstract>
    <identifier type="serial">SC-99-08</identifier>
    <identifier type="opus3-id">397</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3961</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 4th Italian Conference on Algorithms amd Complexity, Vol. 1767 of Lecture Notes in Computer Science, Springer 2000, 125-136</enrichment>
    <author>Dietrich Hauptmeier</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-99-08</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitive analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elevator</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="F.1.2">Modes of Computation</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="MATHEON-C3:Online-Modular">MATHEON-C3:Online-Modular</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/396/SC-99-08.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/396/SC-99-08.pdf</file>
  </doc>
</export-example>
