Name
Abstract | ||
|---|---|---|
We study a variant of the pickup-and-delivery problem (PDP) in which the objects that have to be transported can be reloaded at most d times, for a given d@?N. This problem is known to be polynomially solvable on paths or cycles and NP-complete on trees. We present a (4/3+@e)-approximation algorithm if the underlying graph is a tree. By using a result of Charikar et al. [M. Charikar, C. Chekuri, A. Goel, S. Guha, S. Plotkin, Approximating a finite metric by a small number of tree metrics, in: FOCS '98: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 1998, pp. 379-388], this can be extended to a O(lognloglogn)-approximation for general graphs. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.dam.2008.05.016 | Discrete Applied Mathematics |
Keywords | Field | DocType |
s. plotkin,pickup and delivery,computer science,m. charikar,approximation algorithm,transportation,annual symposium,stacker crane,semi-preemptive routing,c. chekuri,colored arborescences,s. guha,pickup-and-delivery problem,tree metrics,approximation,ieee computer society,dial-a-ride | Approximation algorithm,Discrete mathematics,Graph,Graph algorithms,Combinatorics,Tree (graph theory),Computer society,Mathematics | Journal |
Volume | Issue | ISSN |
156 | 17 | Discrete Applied Mathematics |
Citations | PageRank | References |
1 | 0.38 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven O. Krumke | 1 | 308 | 36.62 |
| Dirk Räbiger | 2 | 1 | 1.06 |
| Rainer Schrader | 3 | 6 | 1.82 |