<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>734</id>
    <completedYear/>
    <publishedYear/>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst/>
    <pageLast/>
    <pageNumber/>
    <edition/>
    <issue/>
    <volume/>
    <type>reportzib</type>
    <publisherName/>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>2003-05-12</completedDate>
    <publishedDate>2003-05-12</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Average Case Analysis of a Hard Dial-a-Ride Problem</title>
    <abstract language="eng">In the dial-a-ride-problem (DARP) objects have to be moved between given sources and destinations in a transportation network by means of a server. The goal is to find a shortest transportation for the server. We study the DARP when the underlying transportation network forms a caterpillar. This special case is strongly NP-hard in the worst case. We prove that in a probabilistic setting there exists a polynomial time algorithm which almost surely finds an optimal solution. Moreover, with high probability the optimality of the solution found can be certified efficiently. We also examine the complexity of the DARP in a semi-random setting and in the unweighted case.</abstract>
    <identifier type="serial">03-12</identifier>
    <identifier type="opus3-id">735</identifier>
    <identifier type="urn">urn:nbn:de:0297-zib-7348</identifier>
    <enrichment key="SourceTitle">An extended abstract appeared in: Proc. of the 6th Workshop on Models and algorithms for Planning and Scheduling Problems. 2003. Pp. 48-50 under the title: Scheduling a server on a caterpillar network - a probabilistic analysis</enrichment>
    <author>Amin Coja-Oghlan</author>
    <author>Sven Krumke</author>
    <author>Till Nierhoff</author>
    <series>
      <title>ZIB-Report</title>
      <number>03-12</number>
    </series>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>dial-a-ride-problem</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>average case analysis</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>MST-heuristic</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>Steiner trees</value>
    </subject>
    <subject>
      <language>eng</language>
      <type>uncontrolled</type>
      <value>NP-hardness</value>
    </subject>
    <collection role="ddc" number="000">Informatik, Informationswissenschaft, allgemeine Werke</collection>
    <collection role="ccs" number="G.2.1">Combinatorics (F.2.2)</collection>
    <collection role="ccs" number="G.2.2">Graph Theory (F.2.2)</collection>
    <collection role="msc" number="68W40">Analysis of algorithms [See also 68Q25]</collection>
    <collection role="institutes" number="">ZIB Allgemein</collection>
    <file>https://opus4.kobv.de/opus4-zib/files/734/ZR-03-12.ps</file>
    <file>https://opus4.kobv.de/opus4-zib/files/734/ZR-03-12.pdf</file>
  </doc>
</export-example>
