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

[thumbnail of zaik2006-511.pdf]
Preview
 PDF
zaik2006-511.pdf - Submitted Version
Download (151kB) | Preview

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.

Item Type: Article
Creators:
Creators
Email
ORCID
ORCID Put Code
Krumke, Sven
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Räbiger, Dirk
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
Schrader, Rainer
UNSPECIFIED
UNSPECIFIED
UNSPECIFIED
URN: urn:nbn:de:hbz:38-548944
Journal or Publication Title: Discrete Applied Mathematics
Volume: 156
Number: 17
Page Range: pp. 3298-3304
Date: 2008
Publisher: Elsevier Science
Language: English
Faculty: Faculty of Mathematics and Natural Sciences
Divisions: Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science
Subjects: Data processing Computer science
Refereed: No
URI: http://kups.ub.uni-koeln.de/id/eprint/54894

Downloads

Downloads per month over past year

Export

Actions (login required)

View Item View Item