<?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>
  <doc>
    <id>689</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-05-07</completedDate>
    <publishedDate>2002-05-07</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online Call Admission in Optical Networks with Larger Wavelength Demands</title>
    <abstract language="eng">In the problem of \emph{Online Call Admission in Optical Networks}, briefly called \textsc{oca}, we are given a graph $G=(V,E)$ together with a set of wavelengths~$W$ and a finite sequence $\sigma=r_1,r_2,\dots$ of calls which arrive in an online fashion. Each call~$r_j$ specifies a pair of nodes to be connected and an integral demand indicating the number of required lightpaths. A lightpath is a path in~$G$ together with a wavelength~$\lambda \in W$. Upon arrival of a call, an online algorithm must decide immediately and irrevocably whether to accept or to reject the call without any knowledge of calls which appear later in the sequence. If the call is accepted, the algorithm must provide the requested number of lightpaths to connect the specified nodes. The essential restriction is the wavelength conflict constraint: each wavelength is available only once per edge, which implies that two lightpaths sharing an edge must have different wavelengths. Each accepted call contributes a benefit equal to its demand to the overall profit. The objective in \textsc{oca} is to maximize the overall profit. Competitive algorithms for \textsc{oca} have been known for the special case where every call requests just a single lightpath. In this paper we present the first competitive online algorithms for the general case of larger demands.</abstract>
    <identifier type="serial">02-22</identifier>
    <identifier type="opus3-id">690</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6890</identifier>
    <enrichment key="SourceTitle">Appeared in: Graph-Theoretic Concepts in Computer Science. 28 Intern. Workshop, WG 2002, Cesky Krumlov, Czech Republic, June 13-15, 2002, revised papers. L. Kucera (ed.) Springer 2002. LNCS 2573. Pp. 333-344</enrichment>
    <author>Sven Krumke</author>
    <author>Diana Poensgen</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-22</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Call Admission</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Routing and Wavelength Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Optical Networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Competitive Analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Colorability</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="msc" number="90B18">Communication networks [See also 68M10, 94A05]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="DynRoute">DynRoute</collection>
    <collection role="projects" number="ONLINE-PLANNING">ONLINE-PLANNING</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/689/ZR-02-22.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/689/ZR-02-22.pdf</file>
  </doc>
</export-example>
