<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>894</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2005-12-22</completedDate>
    <publishedDate>2005-12-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online Target Date Assignment Problem</title>
    <abstract language="eng">Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman.</abstract>
    <identifier type="serial">05-61</identifier>
    <identifier type="opus3-id">894</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-8945</identifier>
    <enrichment key="SourceTitle">Appeared in : T. Erlebach; G. Persiano (eds.), Approximation and Online Algorithms (WAOA 2005), LNCS 3879 (2006) 230-243</enrichment>
    <author>Stefan Heinz</author>
    <author>Sven Krumke</author>
    <author>Nicole Megow</author>
    <author>Jörg Rambau</author>
    <author>Andreas Tuchscherer</author>
    <author>Tjark Vredeveld</author>
    <series>
      <title>ZIB-Report</title>
      <number>05-61</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Target Date Assignment Problem</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68W40">Analysis of algorithms [See also 68Q25]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="projects" number="MATHEON-B14:Comb-Log">MATHEON-B14:Comb-Log</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/894/ZR-05-61.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/894/ZR-05-61.ps</file>
  </doc>
  <doc>
    <id>3355</id>
    <completedYear>2006</completedYear>
    <publishedYear>2006</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>230</pageFirst>
    <pageLast>243</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>3879</volume>
    <type>conferenceobject</type>
    <publisherName>Springer</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online Target Date Assignment Problem</title>
    <parentTitle language="eng">Proc. 3rd Workshop on Approximation and Online Algorithms</parentTitle>
    <identifier type="url">http://opus.kobv.de/zib/volltexte/2005/894/</identifier>
    <enrichment key="Series">Lecture Notes in Computer Science</enrichment>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-8945</enrichment>
    <author>Stefan Heinz</author>
    <editor>Thomas Erlebach</editor>
    <author>Sven Krumke</author>
    <editor>Giuseppe Persiano</editor>
    <author>Nicole Megow</author>
    <author>Jörg Rambau</author>
    <author>Andreas Tuchscherer</author>
    <author>Tjark Vredeveld</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="projects" number="MATHEON-B14:Comb-Log">MATHEON-B14:Comb-Log</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3360</id>
    <completedYear>2009</completedYear>
    <publishedYear>2009</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>71</pageFirst>
    <pageLast>73</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Randomized Online Algorithms for Dynamic Multi-Period Routing Problems</title>
    <parentTitle language="eng">Proceedings of MAPSP</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-11132</enrichment>
    <enrichment key="PeerReviewed">yes</enrichment>
    <author>Benjamin Hiller</author>
    <author>Sven Krumke</author>
    <author>Sleman Saliba</author>
    <author>Andreas Tuchscherer</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MATHEON-B14:Comb-Log">MATHEON-B14:Comb-Log</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>1113</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2009-02-11</completedDate>
    <publishedDate>2009-02-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Randomized Online Algorithms for Dynamic Multi-Period Routing Problems</title>
    <abstract language="eng">The Dynamic Multi-Period Routing Problem DMPRP introduced by Angelelli et al. gives a model for a two-stage online-offline routing problem. At the beginning of each time period a set of customers becomes known. The customers need to be served either in the current time period or in the following. Postponed customers have to be served in the next time period. The decision whether to postpone a customer has to be done online. At the end of each time period, an optimal tour for the customers assigned to this period has to be computed and this computation can be done offline. The objective of the problem is to minimize the distance traveled over all planning periods assuming optimal routes for the customers selected in each period. We provide the first randomized online algorithms for the DMPRP which beat the known lower bounds for deterministic algorithms. For the special case of two planning periods we provide lower bounds on the competitive ratio of any randomized online algorithm against the oblivious adversary. We identify a randomized algorithm that achieves the optimal competitive ratio of $\frac{1+\sqrt{2}}{2}$ for two time periods on the real line. For three time periods, we give a randomized algorithm that is strictly better than any deterministic algorithm.</abstract>
    <identifier type="serial">09-03</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1155</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11132</identifier>
    <enrichment key="SourceTitle">Appeared in: 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (C. Stein, M. Uetz und T. Vredeveld, Hg.), 2009</enrichment>
    <author>Benjamin Hiller</author>
    <submitter>unknown unknown</submitter>
    <author>Sven Krumke</author>
    <author>Sleman Saliba</author>
    <author>Andreas Tuchscherer</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-03</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online-Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Randomisierte Algorithmen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Zweistufiges Problem</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Traveling-Salesman-Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>randomized algorithm</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>two-stage problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>traveling salesman problem</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="68W40">Analysis of algorithms [See also 68Q25]</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="projects" number="MATHEON-B14:Comb-Log">MATHEON-B14:Comb-Log</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1113/ZR_09_03.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1113/ZR_09_03.ps</file>
  </doc>
</export-example>
