Semi-Preemptive Routing on Trees

Krumke, Sven and Räbiger, Dirk and Schrader, Rainer (2008) Semi-Preemptive Routing on Trees.
Published in: Discrete Applied Mathematics Vol. 156 (17). pp. 3298-3304.


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 integer d. This problem is known to be polynomially solvable on paths or cycles and NP-complete on trees. We present a (4/3+epsilon)-approximation algorithm if the underlying graph is a tree. By using a result of Charikar et al. (1998), this can be extended to a O(log n log log n)-approximation for general graphs.

Download: [img] PDF - Preprinted Version
Download (151kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik2006-511
Depositing User: Dirk Räbiger
Date Deposited: 19 Apr 2009 00:00
Last Modified: 09 Jan 2012 16:21