Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem

Please always quote using this URN: urn:nbn:de:0297-zib-10114
  • This thesis deals with a Dial-a-Ride problem on trees and considers both offline and online versions of this problem. We study the behavior of certain algorithms on random instances, i.e. we do probabilistic analysis. The focus is on results describing the typical behavior of the algorithms, i.e. results holding with (asymptotically) high probability. For the offline version, we present a simplified proof of a result of Coja-Oghlan, Krumke und Nierhoff. The results states that some heuristic using a minimum spanning tree to approximate a Steiner tree gives optimal results with high probability. This explains why this heuristic produces optimal solutions quite often. In the second part, probabilistic online versions of the problem are introduced. We study the online strategies REPLAN and IGNORE. Regarding the IGNORE strategy we can show that it works almost optimal under high load with high probability.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Benjamin Hiller
Document Type:Master's Thesis
Tag:Dial-a-Ride problem on trees ; online algorithms; probabilistic analysis
MSC-Classification:68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Qxx Theory of computing / 68Q25 Analysis of algorithms and problem complexity [See also 68W40]
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area) / 68Rxx Discrete mathematics in relation to computer science / 68R10 Graph theory (including graph drawing) [See also 05Cxx, 90B10, 90B35, 90C35]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B06 Transportation, logistics
CCS-Classification:F. Theory of Computation / F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY (B.6-7, F.1.3) / F.2.2 Nonnumerical Algorithms and Problems (E.2-5, G.2, H.2-3)
G. Mathematics of Computing / G.2 DISCRETE MATHEMATICS / G.2.1 Combinatorics (F.2.2)
Contributing Corporation:TU Ilmenau
Publishing Institution:Zuse Institute Berlin (ZIB)
Date of first Publication:2004/12/31

$Rev: 13581 $