ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Euler is Standing in Line (1999)

Hauptmeier, Dietrich ; Krumke, Sven ; Rambau, Jörg ; [et al.]

add to mindlist on the mindlist

Details

Publication Date: 2020-11-13

Description: In this paper we study algorithms for ``Dial-a-Ride'' transportation problems. In the basic version of the problem we are given transportation jobs between the vertices of a graph and the goal is to find a shortest transportation that serves all the jobs. This problem is known to be NP-hard even on trees. We consider the extension when precedence relations between the jobs with the same source are given. Our results include a polynomial time algorithm on paths and an approximation algorithm on general graphs with a performance of~$9/4$. For trees we improve the performance to~$5/3$.

Keywords: ddc:000

Language: English

Type: reportzib , doc-type:preprint

Format: application/postscript

Format: application/pdf

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

OPUS

PDF

Overview

hit 1 - 1 | 1 hit