TY - THES A1 - Hiller, Benjamin T1 - Bad Guys are Rare: Probabilistic Analysis of an Elementary Dial-a-Ride Problem N2 - 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. KW - Dial-a-Ride problem on trees KW - probabilistic analysis KW - online algorithms Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10114 ER -