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.
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 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.
Actions:
Download: |
Download (151kB) | Preview |
---|---|
Editorial actions: | ![]() |
Content information:
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 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/511 |