Name
Abstract | ||
|---|---|---|
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 the 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 that finds an optimal solution with high probability. Moreover, with high probability the optimality of the solution found can be certified efficiently. In addition, we examine the complexity of the Darp in a semirandom setting and in the unweighted case. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/s10951-005-6811-3 | J. Scheduling |
Keywords | Field | DocType |
average-case analysis,NP-hard,approximation algorithm | Flow network,Approximation algorithm,Mathematical optimization,Existential quantification,Computer science,Probabilistic logic,Time complexity,Special case | Journal |
Volume | Issue | ISSN |
8 | 3 | 1094-6136 |
Citations | PageRank | References |
4 | 0.49 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Amin Coja-Oghlan | 1 | 543 | 47.25 |
| Sven O. Krumke | 2 | 308 | 36.62 |
| Till Nierhoff | 3 | 107 | 12.76 |