<?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>913</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2006-04-18</completedDate>
    <publishedDate>2006-04-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">LP-Based Local Approximation for Markov Decision Problems</title>
    <abstract language="eng">The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.\,g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an $\varepsilon$-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies.</abstract>
    <identifier type="serial">06-20</identifier>
    <identifier type="opus3-id">914</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-9131</identifier>
    <author>Stefan Heinz</author>
    <author>Volker Kaibel</author>
    <author>Matthias Peinhardt</author>
    <author>Jörg Rambau</author>
    <author>Andreas Tuchscherer</author>
    <series>
      <title>ZIB-Report</title>
      <number>06-20</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Markov decision problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>linear programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="F.2.2">Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)</collection>
    <collection role="ccs" number="G.2.1">Combinatorics (F.2.2)</collection>
    <collection role="msc" number="68W25">Approximation algorithms</collection>
    <collection role="msc" number="90C40">Markov and semi-Markov decision processes</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>
    <file>https://opus4.kobv.de/opus4-zib/files/913/ZR-06-20.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/913/ZR-06-20.ps</file>
  </doc>
  <doc>
    <id>3209</id>
    <completedYear>2004</completedYear>
    <publishedYear>2004</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>157</pageFirst>
    <pageLast>163</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume>18</volume>
    <type>conferenceobject</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC</title>
    <parentTitle language="eng">Latin-American Conference on Combinatorics, Graphs and Applications, Santiago de Chile 2004</parentTitle>
    <enrichment key="Series">ENDM</enrichment>
    <author>Benjamin Hiller</author>
    <editor>T. Liebling</editor>
    <author>Sven Krumke</author>
    <editor>G. Duran</editor>
    <author>Jörg Rambau</author>
    <editor>M. Matamala</editor>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
  </doc>
  <doc>
    <id>3216</id>
    <completedYear>2006</completedYear>
    <publishedYear>2006</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1897</pageFirst>
    <pageLast>1907</pageLast>
    <pageNumber/>
    <edition/>
    <issue>13</issue>
    <volume>154</volume>
    <type>article</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Reoptimization Gaps versus Model Errors in Online-Dispatching of Service Units for ADAC</title>
    <parentTitle language="eng">DISAM</parentTitle>
    <author>Benjamin Hiller</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
  </doc>
  <doc>
    <id>386</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-01-27</completedDate>
    <publishedDate>1999-01-27</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Generalized Baues Problem for Cyclic Polytopes II</title>
    <abstract language="eng">Given an affine surjection of polytopes $\pi: P \to Q$, the Generalized Baues Problem asks whether the poset of all proper polyhedral subdivisions of $Q$ which are induced by the map $\pi$ has the homotopy type of a sphere. We extend earlier work of the last two authors on subdivisions of cyclic polytopes to give an affirmative answer to the problem for the natural surjections between cyclic polytopes $\pi: C(n,d') \to C(n,d)$ for all $1 \leq d &lt; d' &lt; n$.</abstract>
    <identifier type="serial">SC-98-43</identifier>
    <identifier type="opus3-id">387</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3862</identifier>
    <enrichment key="SourceTitle">Appeared in: Publications de l'Institut Mathematique, Belgrade 66 (1999) 3-15</enrichment>
    <author>Christos A. Athanasiadis</author>
    <author>Jörg Rambau</author>
    <author>Francisco Santos</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-43</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Generalized Baues Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Polyhedral Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Induced Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Poset</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Spherical</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cyclic Polytopes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bistellar Operations</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52B99">None of the above, but in this section</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/386/SC-98-43.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/386/SC-98-43.pdf</file>
  </doc>
  <doc>
    <id>387</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-01-28</completedDate>
    <publishedDate>1999-01-28</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings</title>
    <abstract language="eng">In 1994, Sturmfels gave a polyhedral version of the Cayley Trick of elimination theory: he established an order-preserving bijection between the posets of \emph{coherent} mixed subdivisions of a Minkowski sum $\mathcal{A}_1+\cdots+\mathcal{A}_r$ of point configurations and of \emph{coherent} polyhedral subdivisions of the associated Cayley embedding $\mathcal{C}(\mathcal{A}_1,\dots,\mathcal{A}_r)$. In this paper we extend this correspondence in a natural way to cover also \emph{non-coherent} subdivisions. As an application, we show that the Cayley Trick combined with results of Santos on subdivisions of Lawrence polytopes provides a new independent proof of the Bohne-Dress Theorem on zonotopal tilings. This application uses a combinatorial characterization of lifting subdivisions, also originally proved by Santos.</abstract>
    <identifier type="serial">SC-98-44</identifier>
    <identifier type="opus3-id">388</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3874</identifier>
    <enrichment key="SourceTitle">Appeared in: "The Cayley Trick, lifting subdivisions and the Bohne-Dress theorem on zonotopal tilings", Journal of the European Mathematical Society, 2 (2000) 179-198</enrichment>
    <author>Birkett Huber</author>
    <author>Jörg Rambau</author>
    <author>Francisco Santos</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-44</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Polyhedral subdivision</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>fiber polytope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed subdivision</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lifting subdivision</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Minkowski sum</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cayley Trick</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bohne-Dress Theorem</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="14M25">Toric varieties, Newton polyhedra [See also 52B20]</collection>
    <collection role="msc" number="52B11">n-dimensional polytopes</collection>
    <collection role="msc" number="52B20">Lattice polytopes (including relations with commutative algebra and algebraic geometry) [See also 06A11, 13F20, 13Hxx]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/387/SC-98-44.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/387/SC-98-44.pdf</file>
  </doc>
  <doc>
    <id>367</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-09-22</completedDate>
    <publishedDate>1998-09-22</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Combinatorial Online Optimization</title>
    <abstract language="eng">In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.</abstract>
    <identifier type="serial">SC-98-24</identifier>
    <identifier type="opus3-id">368</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3674</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the International Conference of Operations Research Zürich (OR'98), Springer, 1999, pp. 21-37</enrichment>
    <author>Norbert Ascheuer</author>
    <author>Martin Grötschel</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-24</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitiveness</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>combinatorial optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-world problems</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/367/SC-98-24.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/367/SC-98-24.pdf</file>
  </doc>
  <doc>
    <id>357</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-05-06</completedDate>
    <publishedDate>1998-05-06</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Generalized Baues Problem for Cyclic Polytopes I.</title>
    <abstract language="eng">The Generalized Baues Problem asks whether for a given point configuration the order complex of all its proper polyhedral subdivisions, partially ordered by refinement, is homotopy equivalent to a sphere. In this paper, an affirmative answer is given for the vertex sets of cyclic polytopes in all dimensions. This yields the first non-trivial class of point configurations with neither a bound on the dimension, the codimension, nor the number of vertice for which this is known to be true. Moreover, it is shown that all triangulations of cyclic polytopes are lifting triangulations. This contrasts the fact that in general there are many non-regular triangulations of cyclic polytopes. Beyond this, we find triangulations of $C(11,5)$ with flip deficiency. This proves---among other things---that there are triangulations of cyclic polytopes that are non-regular for every choice of points on the moment curve.</abstract>
    <identifier type="serial">SC-98-14</identifier>
    <identifier type="opus3-id">358</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3579</identifier>
    <enrichment key="SourceTitle">Appeared in: European Journal of Combinatorics, 21(1), 2000, 65-83</enrichment>
    <author>Jörg Rambau</author>
    <author>Francisco Santos</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-14</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Generalized Baues Problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Polyhedral Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Induced Subdivisions</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Poset</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Spherical</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cyclic Polytopes</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Bistellar Operations</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Flip Defici</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52B99">None of the above, but in this section</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/357/SC-98-14.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/357/SC-98-14.pdf</file>
  </doc>
  <doc>
    <id>377</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1998-12-08</completedDate>
    <publishedDate>1998-12-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online Transportation Problem: Competitive Scheduling of Elevators</title>
    <abstract language="eng">In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service.</abstract>
    <identifier type="serial">SC-98-34</identifier>
    <identifier type="opus3-id">378</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-3779</identifier>
    <enrichment key="SourceTitle">Appeared as: Online Dial-a-Ride Problems: in: Minimizing the Completion Time. Proceeding of the 17th International Symposium on Theoretical Aspects of Computer Science, Vol 1770 of Lecture Notes in Computer Science, Springer 2000, 639-650</enrichment>
    <author>Norbert Ascheuer</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-98-34</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>
    <file>https://opus4.kobv.de/opus4-zib/files/377/SC-98-34.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/377/SC-98-34.pdf</file>
  </doc>
  <doc>
    <id>3144</id>
    <completedYear>2001</completedYear>
    <publishedYear>2001</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>679</pageFirst>
    <pageLast>704</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>bookpart</type>
    <publisherName>Springer</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Combinatorial Online Optimization in Real Time</title>
    <parentTitle language="eng">Online Optimization of Large Scale Systems</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-6424</enrichment>
    <author>Martin Grötschel</author>
    <editor>Martin Grötschel</editor>
    <author>Sven Krumke</author>
    <editor>Sven Krumke</editor>
    <author>Jörg Rambau</author>
    <editor>Jörg Rambau</editor>
    <author>Thomas Winter</author>
    <author>Uwe Zimmermann</author>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="MATHEON-C3:Online-Modular">MATHEON-C3:Online-Modular</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>3143</id>
    <completedYear>2001</completedYear>
    <publishedYear>2001</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>705</pageFirst>
    <pageLast>729</pageLast>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>bookpart</type>
    <publisherName>Springer</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online Optimization of Complex Transportation Systems</title>
    <parentTitle language="eng">Online Optimization of Large Scale Systems</parentTitle>
    <enrichment key="PreprintUrn">urn:nbn:de:0297-zib-6438</enrichment>
    <author>Martin Grötschel</author>
    <editor>Martin Grötschel</editor>
    <author>Sven Krumke</author>
    <editor>Sven Krumke</editor>
    <author>Jörg Rambau</author>
    <editor>Jörg Rambau</editor>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="2010-C3-INAD">2010-C3-INAD</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
  </doc>
  <doc>
    <id>711</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-11-25</completedDate>
    <publishedDate>2002-11-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online-Dispatching of Automobile Service Units</title>
    <abstract language="eng">We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association.</abstract>
    <identifier type="serial">02-44</identifier>
    <identifier type="opus3-id">712</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7117</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2002. Selected Papers of the International Conference on Operations Research (SOR 2002), Klagenfurt, September 2-5, 2002. U. Leopold-Wildburger et al. (eds.) Berlin: Springer 2003. Pp. 168-173</enrichment>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Luis Miguel Torres</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-44</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>soft time windows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-time</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ADAC</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/711/ZR-02-44.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/711/ZR-02-44.pdf</file>
  </doc>
  <doc>
    <id>702</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">Dynamic Routing Algorithms in Transparent Optical Networks An Experimental Study Based on Real Data</title>
    <abstract language="eng">Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not used continuously. At this point, dynamic provisioning could increase the utilization of network resources. WDM based Optical Transport Networks (OTNs) will shortly allow for fast dynamic network reconfiguration. This enables optical broadband leased line services on demand. Since service requests competing for network resources may lead to service blocking, it is vital to use appropriate strategies for routing and wavelength assignment in transparent optical networks. We simulate the service blocking probabilities of various dynamic algorithms for this problem using a well-founded traffic model for two realistic networks. One of the algorithms using shortest path routings performs best on all instances. Surprisingly, the tie-breaking rule between equally short paths in different wavelengths decides between success or failure.</abstract>
    <identifier type="serial">02-35</identifier>
    <identifier type="opus3-id">703</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7025</identifier>
    <enrichment key="SourceTitle">Appeared in: Proceedings of the 7th IFIP Working Conference on Optical Network Design and Modelling (ONDM 2003) (Cinklar, Tibor and Jacab, Tivadar and Tapolcai, Janos and Gaspar, Csaba, eds.) Kluwer Acadamic Press(2003) 293-312</enrichment>
    <author>Ralf Hülsermann</author>
    <author>Monika Jäger</author>
    <author>Sven Krumke</author>
    <author>Diana Poensgen</author>
    <author>Jörg Rambau</author>
    <author>Andreas Tuchscherer</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-35</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Dynamic Network Configuration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Routing and Wavelength Allocation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Transparent Optical Networks</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Blocking Probability</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Simulation</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</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>
    <file>https://opus4.kobv.de/opus4-zib/files/702/ZR-02-35.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/702/ZR-02-35.pdf</file>
  </doc>
  <doc>
    <id>684</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-04-08</completedDate>
    <publishedDate>2002-04-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">TOPCOM: Triangulations of Point Configurations and Oriented Matroids</title>
    <abstract language="eng">TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed.</abstract>
    <identifier type="serial">02-17</identifier>
    <identifier type="opus3-id">685</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6849</identifier>
    <enrichment key="SourceTitle">Appeared in: Mathematical Software - ICMS 2002 (Cohen, Arjeh M. and Gao, Xiao-Shan and Takayama, Nobuki, eds.) World Scientific (2002) 330-340</enrichment>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-17</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>triangulation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>point configuration</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>oriented matroid</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chirotope</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>circuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cocircuit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>symmetry</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>TOPCOM</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52C22">Tilings in n dimensions [See also 05B45, 51M20]</collection>
    <collection role="msc" number="52C35">Arrangements of points, flats, hyperplanes [See also 32S22]</collection>
    <collection role="msc" number="52C40">Oriented matroids</collection>
    <collection role="msc" number="52C45">Combinatorial complexity of geometric structures [See also 68U05]</collection>
    <collection role="msc" number="68R05">Combinatorics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/684/ZR-02-17.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/684/ZR-02-17.pdf</file>
  </doc>
  <doc>
    <id>685</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-04-08</completedDate>
    <publishedDate>2002-04-08</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Making the Yellow Angels Fly: Online Dispatching Of Service Vehicles in Real Time</title>
    <abstract language="eng">Combinatorial online optimization is an area with lots of applications and potential for significant progress, both in theory and practice. In this short note we sketch the ADACproblem, a typical large-scale online optimization problem, discuss some theoretical and pratical issues coming up, and explain, very briefly, how we approach this problem mathematically. Online problems are a battlefield of heuristics with many strong claims about their solution quality. We indicate that a stronger problem orientation and the use of a little more mathematics may yield.</abstract>
    <identifier type="serial">02-18</identifier>
    <identifier type="opus3-id">686</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6858</identifier>
    <enrichment key="SourceTitle">Appeared in: SIAM News, Vol. 35, No. 4, (2002) pp. 10-11</enrichment>
    <author>Martin Grötschel</author>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Luis Miguel Torres</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-18</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle dispatching</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>soft time windows</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real-time</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>column generation</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>pricing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch and bound</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>real world data</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>ADAC</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="groetschel">Grötschel, Martin</collection>
    <collection role="projects" number="ADAC-Dispatch">ADAC-Dispatch</collection>
    <collection role="projects" number="MATHEON-C6:Online-Reopt">MATHEON-C6:Online-Reopt</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/685/ZR-02-18.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/685/ZR-02-18.pdf</file>
  </doc>
  <doc>
    <id>690</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">How to Cut a Cake Almost Fairly</title>
    <abstract language="eng">In the cake cutting problem, $n\ge2$ players want to cut a cake into $n$ pieces so that every player gets a ``fair'' share of the cake by his own measure. We describe a protocol with $n-1$~cuts in which each player can enforce to get a share of at least~$1/(2n-2)$. Moreover we show that no protocol with $n-1$~cuts can guarantee a better fraction.</abstract>
    <identifier type="serial">02-23</identifier>
    <identifier type="opus3-id">691</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6905</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, 2002, pp. 263-264</enrichment>
    <author>Sven Krumke</author>
    <author>Maarten Lipmann</author>
    <author>Willem de Paepe</author>
    <author>Diana Poensgen</author>
    <author>Jörg Rambau</author>
    <author>Leen Stougie</author>
    <author>Gerhard Woeginger</author>
    <series>
      <title>ZIB-Report</title>
      <number>02-23</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Fair division</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cake cutting</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="91A06">n-person games, n &gt; 2</collection>
    <collection role="msc" number="91A10">Noncooperative games</collection>
    <collection role="msc" number="91A80">Applications of game theory</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/690/ZR-02-23.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/690/ZR-02-23.pdf</file>
  </doc>
</export-example>
