<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>621</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-12-19</completedDate>
    <publishedDate>2000-12-19</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem</title>
    <abstract language="eng">In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most $C$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.</abstract>
    <identifier type="serial">00-53</identifier>
    <identifier type="opus3-id">622</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6217</identifier>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <author>Steffen Weider</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-53</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NP-completeness</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>polynomial-time approximation algorithms</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>stacker-crane problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>vehicle</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="68Q10">Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85]</collection>
    <collection role="msc" number="68Q25">Analysis of algorithms and problem complexity [See also 68W40]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <collection role="persons" number="weider">Weider, Steffen</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/621/ZR-00-53.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/621/ZR-00-53.pdf</file>
  </doc>
  <doc>
    <id>623</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-12-20</completedDate>
    <publishedDate>2000-12-20</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Online Optimierung</title>
    <abstract language="eng">Wie soll man einen Aufzug steuern, wenn man keine Informationen über zukünftige Fahraufträge besitzt? Soll man eine Bahncard kaufen, wenn die nächsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollständig gegeben sind. In vielen Fällen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungenügend. Zahlreiche Problemstellungen in der Praxis sind in natürlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zukünftiger Ereignisse getroffen werden müssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten Lösung mit dem Wert einer optimalen Offline-Lösung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schwächen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine Fülle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So müssen Entscheidungen unter strikten Zeitbeschränkungen gefällt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgewählte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universität Berlin entstanden.</abstract>
    <identifier type="serial">00-55</identifier>
    <identifier type="opus3-id">624</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6238</identifier>
    <author>Sven Krumke</author>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-55</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Kompetitive Analyse</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online Optimierung</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Online Algorithmen</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="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/623/ZR-00-55.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/623/ZR-00-55.pdf</file>
  </doc>
  <doc>
    <id>613</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-12-11</completedDate>
    <publishedDate>2000-12-11</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Circuit Admissible Triangulations of Oriented Matroids</title>
    <abstract language="eng">All triangulations of euclidean oriented matroids are of the same PL-homeomorphism type by a result of Anderson. That means all triangulations of euclidean acyclic oriented matroids are PL-homeomorphic to PL-balls and that all triangulations of totally cyclic oriented matroids are PL-homeomorphic to PL-spheres. For non-euclidean oriented matroids this question is wide open. One key point in the proof of Anderson is the following fact: for every triangulation of a euclidean oriented matroid the adjacency graph of the set of all simplices ``intersecting'' a segment $[p_-p_+]$ is a path. We call this graph the $[p_-p_+]$-adjacency graph of the triangulation. While we cannot solve the problem of the topological type of triangulations of general oriented matroids we show in this note that for every circuit admissible triangulation of an arbitrary oriented matroid the $[p_-p_+]$-adjacency graph is a path.</abstract>
    <identifier type="serial">00-45</identifier>
    <identifier type="opus3-id">614</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6139</identifier>
    <enrichment key="SourceTitle">Appeared in: Discrete u. Computational Geometry, Vol. 27, No. 1 (2002) 155-161</enrichment>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-45</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>triangulations of oriented matroids</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>topological type</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>segment adjacency graph</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52C40">Oriented matroids</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/613/ZR-00-45.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/613/ZR-00-45.pdf</file>
  </doc>
  <doc>
    <id>614</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>deu</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2000-12-12</completedDate>
    <publishedDate>2000-12-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="deu">Triangulierungen von Punktmengen und Polyedern</title>
    <abstract language="deu">Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung über Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterführende Themen reguläre Triangulierungen, Sekundärpolytope, bistellare Operationen, höhere Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel über Enumeration und Optimierung beschließt die Zusammenstellung.</abstract>
    <identifier type="serial">00-46</identifier>
    <identifier type="opus3-id">615</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-6145</identifier>
    <author>Jörg Rambau</author>
    <series>
      <title>ZIB-Report</title>
      <number>00-46</number>
    </series>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>point configuration</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>triangulation</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>polytope</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>polyhedron</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>Gale diagram</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>secondary polytope</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>cyclic polytope</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>graph of all triangulations</value>
    </subject>
    <subject>
      <language>deu</language>
      <type>uncontrolled</type>
      <value>conn</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="msc" number="52B05">Combinatorial properties (number of faces, shortest paths, etc.) [See also 05Cxx]</collection>
    <collection role="msc" number="52B11">n-dimensional polytopes</collection>
    <collection role="msc" number="52B35">Gale and other diagrams</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="52B55">Computational aspects related to convexity (For computational geometry and algorithms, see 68Q25, 68U05; for numerical algorithms, see 65Yxx) [See also 68Uxx]</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="institutes" number="">ZIB Allgemein</collection>
    <collection role="projects" number="ZIB-PolSub">ZIB-PolSub</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/614/ZR-00-46.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/614/ZR-00-46.pdf</file>
  </doc>
</export-example>
