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: [img] PDF - Preprinted Version
Download (151kB) | Preview
Editorial actions: View Item View Item (Login required)
Content information:
Item Type: Article
Citations: 2 (Google Scholar) | 1 (Web of Science)
Uncontrolled Keywords: dial-a-ride pickup and delivery transportation approximation colored arborescences stacker crane
Subjects:
  • 05-XX Combinatorics > 05Cxx Graph theory > 05C45 Eulerian and Hamiltonian graphs

  • 90-XX Operations research, mathematical programming > 90Cxx Mathematical programming > 90C39 Dynamic programming

  • 68-XX Computer science > 68Rxx Discrete mathematics in relation to computer science > 68R05 Combinatorics

  • 90-XX Operations research, mathematical programming > 90Bxx Operations research and management science > 90B06 Transportation, logistics

    		•
    Divisions: Institute of Computer Science > Computer Science Department - Prof. Dr. Schrader
    Mathematical Institute > Prof. Dr. Faigle
    Related URLs:
    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