Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 5 of 5
Back to Result List

Average Case Analysis of a Hard Dial-a-Ride Problem

Please always quote using this URN: urn:nbn:de:0297-zib-7348
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Amin Coja-Oghlan, Sven Krumke, Till Nierhoff
Document Type:ZIB-Report
Tag:MST-heuristic; NP-hardness; Steiner trees; average case analysis; dial-a-ride-problem
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Wxx Algorithms (For numerical algorithms, see 65-XX; for combinatorics and graph theory, see 05C85, 68Rxx) / 68W40 Analysis of algorithms [See also 68Q25]
CCS-Classification:G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.1 Combinatorics (F.2.2)
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.2 Graph Theory (F.2.2)
Date of first Publication:2003/05/12
Series (Serial Number):ZIB-Report (03-12)
ZIB-Reportnumber:03-12
Published in: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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.