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 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.
|Depositing User:||Dirk Räbiger|
|Date Deposited:||19 Apr 2009 00:00|
|Last Modified:||09 Jan 2012 16:21|