<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>1120</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-25</completedDate>
    <publishedDate>2009-02-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Discrete Optimization in Public Transportation</title>
    <abstract language="eng">The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.</abstract>
    <abstract language="deu">Die mathematische Behandlung von Planungsproblemen im öffentlichen Verkehr hat im letzten Jahrzehnt große Fortschritte gemacht. Klassische Probleme wie die Umlauf- und die Dienstplanung können heutzutage routinemäßig mit kombinatorischen Optimierungsmethoden gelöst werden. Die Behandlung von Problemen der Angebotsplanung und der Betriebssteuerung sind dagegen noch nicht ganz auf diesem Stand. Dieser Artikel gibt einen Überblick über den Stand der Forschung, über wichtige Entwicklungen und einige Herausforderungen in diesem Gebiet. Die Vision ist, dass mathematische Planungswerkzeuge im öffentlichen Verkehr (Computer Aided Scheduling, CAS) in Zukunft eine ähnliche Rolle spielen werden wie CAD-Systeme in der industriellen Fertigung.</abstract>
    <identifier type="serial">08-56</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1168</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11207</identifier>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>08-56</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Öffentlicher Verkehr</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Nahverkehr</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Optimierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Public Transit</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Optimization</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B20">Traffic problems</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1120/ZR_08_56.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1120/ZR_08_56.ps</file>
  </doc>
  <doc>
    <id>1114</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-13</completedDate>
    <publishedDate>2009-02-13</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Fare Planning for Public Transport</title>
    <abstract language="eng">In this paper we investigate the fare planning model for public transport, which consists in designing a system of fares maximizing the revenue. We discuss a discrete choice model in which passengers choose between different travel alternatives to express the demand as a function of fares. Furthermore, we give a computational example for the city of Potsdam and discuss some theoretical aspects.</abstract>
    <identifier type="serial">09-04</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1160</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11144</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2006. K. H. Waldmann, U. M. Stocker (eds.) Springer 2007, pp. 61-66</enrichment>
    <author>Marika Neumann</author>
    <submitter>unknown unknown</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>09-04</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>fares</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>descrete choice</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="traffic">Mathematics of Transportation and Logistics</collection>
    <collection role="projects" number="MATHEON-B1">MATHEON-B1</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1114/ZR_09_04.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1114/ZR_09_04.ps</file>
  </doc>
  <doc>
    <id>1115</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-17</completedDate>
    <publishedDate>2009-02-17</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Improving the performance of elevator systems using exact reoptimization algorithms</title>
    <abstract language="eng">This extended abstract is about algorithms for controlling elevator systems employing destination hall calls, i.e. the passenger provides his destination floor when calling an elevator. We present the first exact algorithm for controlling a group of elevators and report on simulation results indicating that destination hall call systems outperform conventional systems.</abstract>
    <identifier type="serial">09-05</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1161</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11155</identifier>
    <enrichment key="SourceTitle">Appeared in: Models and Algorithms for Optimization in Logistics (C. Barnhart, U. Clausen, U. Lauther und R. H. Möhring, eds.), Dagstuhl Seminar Proceedings, Nr. 09261, Schloß Dagstuhl, Leibniz-Zentrum für Informatik, Germany, 2009 and 9th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP 2009) (C. Stein, M. Uetz und T. Vredeveld, eds.), 2009</enrichment>
    <author>Benjamin Hiller</author>
    <submitter>unknown unknown</submitter>
    <author>Torsten Klug</author>
    <author>Andreas Tuchscherer</author>
    <series>
      <title>ZIB-Report</title>
      <number>09-05</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Aufzugssteuerung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Onlineoptimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Exakte Reoptimierung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>elevator control</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>exact reoptimation</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="ccs" number="C.4">PERFORMANCE OF SYSTEMS</collection>
    <collection role="ccs" number="J.7">COMPUTERS IN OTHER SYSTEMS (C.3)</collection>
    <collection role="msc" number="65K05">Mathematical programming methods [See also 90Cxx]</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C90">Applications of mathematical programming</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="klug">Klug, Torsten</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/1115/ZR_09_05.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1115/ZR_09_05.ps</file>
  </doc>
  <doc>
    <id>1095</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-10-31</completedDate>
    <publishedDate>2008-10-31</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Constraint Integer Programming: Techniques and Applications</title>
    <abstract language="eng">This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.</abstract>
    <identifier type="serial">08-43</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1132</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10950</identifier>
    <author>Tobias Achterberg</author>
    <submitter>unknown unknown</submitter>
    <author>Timo Berthold</author>
    <author>Stefan Heinz</author>
    <author>Thorsten Koch</author>
    <author>Kati Wolter</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-43</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>constraint programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>mixed integer programming</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>branch-and-cut</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>optimization software</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>chip verification</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="achterberg">Achterberg, Tobias</collection>
    <collection role="persons" number="berthold">Berthold, Timo</collection>
    <collection role="persons" number="heinz">Heinz, Stefan</collection>
    <collection role="persons" number="koch">Koch, Thorsten</collection>
    <collection role="projects" number="MATHEON-B12:IPSym">MATHEON-B12:IPSym</collection>
    <collection role="projects" number="VeriCount">VeriCount</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1095/ZR_08_43.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1095/ZR_08_43.ps</file>
  </doc>
  <doc>
    <id>1086</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation>ZIB</creatingCorporation>
    <contributingCorporation>EPN Quito</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-08-19</completedDate>
    <publishedDate>2008-08-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System</title>
    <abstract language="eng">Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.</abstract>
    <identifier type="serial">08-35</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1120</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10869</identifier>
    <enrichment key="SourceTitle">Appeared in: ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems. Matteo Fischetti and Peter Widmayer (eds.) Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2008</enrichment>
    <author>Luis Miguel Torres</author>
    <submitter>unknown unknown</submitter>
    <author>Ramiro Torres</author>
    <author>Ralf Borndörfer</author>
    <author>Marc Pfetsch</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-35</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>line planning</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>computational complexity</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>public transport</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>integer programming</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90B06">Transportation, logistics</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="MATHEON-B15">MATHEON-B15</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1086/ZR_08_35.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1086/ZR_08_35.ps</file>
  </doc>
  <doc>
    <id>1105</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation>Warsaw University of Technology</contributingCorporation>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-12-18</completedDate>
    <publishedDate>2008-12-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the complexity of column generation in survivable network design with path-based survivability mechanisms</title>
    <abstract language="eng">This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures.</abstract>
    <identifier type="serial">08-51</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1146</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11058</identifier>
    <author>Sebastian Orlowski</author>
    <submitter>unknown unknown</submitter>
    <author>Michal Pióro</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-51</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Netzplanung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Dimensionierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Spaltengenerierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Mehrfachausfälle</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>survivable network design</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>routing</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>complexity</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="68M10">Network design and communication [See also 68R10, 90B18]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="msc" number="90C08">Special problems of linear programming (transportation, multi-index, etc.)</collection>
    <collection role="msc" number="90C35">Programming involving graphs or networks [See also 90C27]</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1105/ZR_08_51.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1105/ZR_08_51.ps</file>
  </doc>
  <doc>
    <id>1102</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-12-10</completedDate>
    <publishedDate>2008-12-10</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra</title>
    <abstract language="eng">Given a combinatorial optimization problem and a subset $N$ of natural numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of $N$. In this paper we briefly touch on questions that addresses common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on polytopes associated with cardinality constrained combinatorial optimization problems. Given an integer programming formulation for a combinatorial optimization problem, by essentially adding Grötschel's cardinality forcing inequalities, we obtain an integer programming formulation for its cardinality restricted version. Since the cardinality forcing inequalities in their original form are mostly not facet defining for the associated polyhedra, we discuss possibilities to strengthen them.</abstract>
    <identifier type="serial">08-48</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1140</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-11026</identifier>
    <author>Rüdiger Stephan</author>
    <submitter>unknown unknown</submitter>
    <series>
      <title>ZIB-Report</title>
      <number>08-48</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Combinatorial Optimization</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cardinality Constraints</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Matroids</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Cardinality Forcing Inequalities</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="05B35">Matroids, geometric lattices [See also 52B40, 90C27]</collection>
    <collection role="msc" number="05C38">Paths and cycles [See also 90B10]</collection>
    <collection role="msc" number="52B40">Matroids (realizations in the context of convex polytopes, convexity in combinatorial structures, etc.) [See also 05B35, 52Cxx]</collection>
    <collection role="msc" number="90C27">Combinatorial optimization</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1102/ZR_08_48.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1102/ZR_08_48.ps</file>
  </doc>
  <doc>
    <id>1092</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-09-25</completedDate>
    <publishedDate>2008-09-25</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">On the optimality of Least Recently Used</title>
    <abstract language="eng">It is well known that competitive analysis yields too pessimistic results when applied to the paging problem and it also cannot make a distinction between many paging strategies. Many deterministic paging algorithms achieve the same competitive ratio, ranging from inefficient strategies as flush-when-full to the good performing least-recently-used (LRU). In this paper, we study this fundamental online problem from the viewpoint of stochastic dominance. We show that when sequences are drawn from distributions modelling locality of reference, LRU is stochastically better than any other online paging algorithm.</abstract>
    <identifier type="serial">08-39</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1124</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10928</identifier>
    <author>Benjamin Hiller</author>
    <submitter>unknown unknown</submitter>
    <author>Tjark Vredeveld</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-39</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Paging</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>locality of reference</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>LRU</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Onlinealgorithmen</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Stochastische Dominanz</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>paging</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>locality of reference</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>LRU</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>online algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>stochastic dominance</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1092/ZR_08_39.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1092/stochasticDominancePaging.pdf</file>
  </doc>
  <doc>
    <id>1099</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-12-05</completedDate>
    <publishedDate>2008-12-05</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Fair Ticket Prices in Public Transport</title>
    <abstract language="eng">Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.</abstract>
    <identifier type="serial">08-46</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1136</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10999</identifier>
    <enrichment key="SourceTitle">A rev. vers. appeared in: H.-G. Bock, X. P. Hoang, R. Rannacher, and J. P. Schlöder (eds.), Modeling, Simulation and Optimization of Complex Processes, Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2 – 6, 2009, Hanoi, Vietnam, pages 53 – 64. Springer Verlag, 2012.</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Nam-Dung Hoang</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-46</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Ticket prices</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>cost allocation game</value>
    </subject>
    <collection role="ddc" number="510">Mathematik</collection>
    <collection role="msc" number="90C10">Integer programming</collection>
    <collection role="msc" number="91A12">Cooperative games</collection>
    <collection role="msc" number="91A46">Combinatorial games</collection>
    <collection role="msc" number="91B24">Price theory and market structure</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="projects" number="ZIB-CostShare">ZIB-CostShare</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1099/ZR_08_46.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1099/ZR_08_46.ps</file>
  </doc>
  <doc>
    <id>1085</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2008-08-18</completedDate>
    <publishedDate>2008-08-18</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Vickrey Auctions for Railway Tracks</title>
    <abstract language="eng">We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.</abstract>
    <identifier type="serial">08-34</identifier>
    <identifier type="issn">1438-0064</identifier>
    <identifier type="opus3-id">1122</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-10855</identifier>
    <enrichment key="SourceTitle">Appeared in: Operations Research Proceedings 2008. Bernhard Fleischmann ... (eds.) Springer 2009, pp. 551-556</enrichment>
    <author>Ralf Borndörfer</author>
    <submitter>unknown unknown</submitter>
    <author>Annette Mura</author>
    <author>Thomas Schlechte</author>
    <series>
      <title>ZIB-Report</title>
      <number>08-34</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Vickrey Auktion</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Fahrplanung</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Vickrey Auction</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Track Allocation Problem</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="institutes" number="optimization">Mathematical Optimization</collection>
    <collection role="persons" number="borndoerfer">Borndörfer, Ralf</collection>
    <collection role="persons" number="schlechte">Schlechte, Thomas</collection>
    <collection role="institutes" number="aopt">Applied Optimization</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/1085/ZR_08_34.pdf</file>
    <file>https://opus4.kobv.de/opus4-zib/files/1085/ZR_08_34.ps</file>
  </doc>
</export-example>
