<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>189</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>1995-10-10</completedDate>
    <publishedDate>1995-10-10</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Solving Stochastic Programs with Complete Integer Recourse: a framework using Gröbner Bases</title>
    <abstract language="eng">In this paper we present a framework for solving stochastic programs with complete integer recourse and discretely distributed right-hand side vector, using Gröbner basis methods from computational algebra to solve the numerous second-stage integer programs. Using structural properties of the integer expected recourse function, we prove that under mild conditions an optimal solution is contained in a finite set. Furthermore, we present a basic scheme to enumerate this set and suggest possible improvements to economize on the number of function evaluations needed.</abstract>
    <identifier type="serial">SC-95-23</identifier>
    <identifier type="opus3-id">189</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-1890</identifier>
    <enrichment key="SourceTitle">Appeared under the title: Solving stochastic programs with integer recourse by enumeration: A framework using Gröbner basis reductions in: Mathematical Programming 83 (1998) 229-252</enrichment>
    <author>Rüdiger Schultz</author>
    <author>Leen Stougie</author>
    <author>Maarten H. van der Vlerk</author>
    <series>
      <title>ZIB-Report</title>
      <number>SC-95-23</number>
    </series>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/189/SC-95-23.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/189/SC-95-23.pdf</file>
  </doc>
  <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>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>
  <doc>
    <id>577</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-03-23</completedDate>
    <publishedDate>2000-03-23</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">The Online-TSP Against Fair Adversaries</title>
    <abstract language="eng">In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~$3/2$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio $\frac{1+\sqrt{17}}{4}\approx 1.28$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.</abstract>
    <identifier type="serial">00-09</identifier>
    <identifier type="opus3-id">578</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-5779</identifier>
    <enrichment key="SourceTitle">Appeared in: Informs Journal on Computing 13 (2001) pp. 138-148. A prel. vers. appeared in: Proc. of the 4th Italian Conference on Algorithms and Complexity, Lecture Notes in Computer Science, vol. 1767, Springer 2000, 137-149</enrichment>
    <author>Michiel Blom</author>
    <author>Sven Krumke</author>
    <author>Willem de Paepe</author>
    <author>Leen Stougie</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-09</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Vehicle Routing</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online-Algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Competitive Analysis</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/577/ZR-00-09.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/577/ZR-00-09.ps</file>
  </doc>
  <doc>
    <id>633</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2001-04-02</completedDate>
    <publishedDate>2001-04-02</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Online Bin-Coloring</title>
    <abstract language="eng">We introduce a new problem that was motivated by a (more complicated) problem arising in a robotized assembly enviroment. The bin coloring problem is to pack unit size colored items into bins, such that the maximum number of different colors per bin is minimized. Each bin has size~$B\in\mathbb{N}$. The packing process is subject to the constraint that at any moment in time at most $q\in\mathbb{N}$ bins may be partially filled. Moreover, bins may only be closed if they are filled completely. An online algorithm must pack each item must be packed without knowledge of any future items. We investigate the existence of competitive online algorithms for the online uniform binpacking problem. We show upper bounds for the bin coloring problem. We prove an upper bound of $3q$ - 1 and a lower bound of $2q$ for the competitive ratio of a natural greedy-type algorithm, and show that surprisingly a trivial algorithm which uses only one open bin has a strictly better competitive ratio of $2q$ - 1. Morever, we show that any deterministic algorithm has a competitive ratio $\Omega (q)$ and that randomization does not improve this lower bound even when the adversary is oblivious.</abstract>
    <identifier type="serial">01-07</identifier>
    <identifier type="opus3-id">634</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6338</identifier>
    <enrichment key="SourceTitle">Appeared in: Proc. of the 9th European Symposium on Algorithms, Springer 2001, LNCS 2161, pp. 74-84</enrichment>
    <author>Sven Krumke</author>
    <author>Willem de Paepe</author>
    <author>Jörg Rambau</author>
    <author>Leen Stougie</author>
    <series>
      <title>ZIB-Report</title>
      <number>01-07</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Online Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>randomized algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>lower bounds</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>competitive analysis</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="ONLINE-PLANNING">ONLINE-PLANNING</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/633/ZR-01-07.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/633/ZR-01-07.pdf</file>
  </doc>
</export-example>
