Universität zu Köln

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

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:	Journal 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