68Q25 Analysis of algorithms and problem complexity [See also 68W40]
Filtern
Erscheinungsjahr
- 1999 (1)
Dokumenttyp
- ZIB-Report (1)
Sprache
- Englisch (1) (entfernen)
Volltext vorhanden
- ja (1)
Gehört zur Bibliographie
- nein (1)
Schlagworte
Institut
- ZIB Allgemein (1)
Euler is Standing in Line
(1999)
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$.