Semi-preemptive routing on trees
We study a variant of the pickup-and-delivery problem (PDP) in which the objects that have to be transported can be reloaded at mostd d times, for a given d?N d ? N . This problem is known to be polynomially solvable on paths or cycles and NP-complete on trees. We present a (4/3+?) ( 4 / 3 + ? ) -approximation algorithm if the underlying graph is a tree. By using a result of Charikar etal. [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. 379388], this can be extended to a O(lognloglogn) O ( log n log log n ) -approximation for general graphs.
transportation approximation pickup and delivery dial-a-ride colored arborescences stacker crane