Euler is Standing in Line
Zitieren Sie bitte immer diese URN: urn:nbn:de:0297-zib-3947
- In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.
Verfasserangaben: | Dietrich Hauptmeier, Sven Krumke, Jörg Rambau, Hans-Christoph Wirth. |
---|---|
Dokumentart: | ZIB-Report |
Freies Schlagwort / Tag: | Eulerian Cycle; NP-completeness; elevator system; polynomial-time approximation algorithms; stacker-crane problem; vehicle routing |
MSC-Klassifikation: | 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 / 68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) [See also 68Q85] |
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] | |
Datum der Erstveröffentlichung: | 03.03.1999 |
Schriftenreihe (Bandnummer): | ZIB-Report (SC-99-06) |
ZIB-Reportnummer: | SC-99-06 |
Verlagspublikation: | Appeared in: Discrete Appl. Math. 113 (2001) 87-107. A prel. vers. appeared in: Proc. of the 25nd Intern. Workshop on Graph-Theoretic Concepts in Computer Science (WG'99), Lecture Notes in Computer Science, vol. 1665, Springer (1999) 42-54 |