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 most dd times, for a given d∈Nd∈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 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)O(lognloglogn)-approximation for general graphs.