TY - CHAP A1 - Hülsermann, Ralf A1 - Jäger, Monika A1 - Poensgen, Diana A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Tuchscherer, Andreas ED - Cinkler, Tibor ED - Jakab, Tivadar ED - Tapolcai, Jànos ED - Gàspàr, Csaba T1 - Dynamic routing algorithms in transparent optical networks T2 - Proceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling (ONDM 2003) Y1 - 2003 UR - http://opus.kobv.de/zib/volltexte/2002/703/ SP - 293 EP - 312 PB - Kluwer Academic Press ER - TY - GEN A1 - Coja-Oghlan, Amin A1 - Krumke, Sven A1 - Nierhoff, Till T1 - Average Case Analysis of a Hard Dial-a-Ride Problem N2 - 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. T3 - ZIB-Report - 03-12 KW - dial-a-ride-problem KW - average case analysis KW - MST-heuristic KW - Steiner trees KW - NP-hardness Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7348 ER -