MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Hall, Alex
Langkau, Katharina
Skutella, Martin		dblp
dblp
dblp
Not MPG Author(s):
Hall, Alex
Langkau, Katharina
Editor(s):
Arora, Sanjeev
Jansen, Klaus
Rolim, Jose D. P.
Sahai, Amit		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Arora, Sanjeev
Jansen, Klaus
Rolim, Jose D. P.
Sahai, Amit
BibTeX cite key*:
HallLangkauSkutella2003
Title, Booktitle
Title*:
An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times
Booktitle*:
Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003
Event, URLs
Conference URL::
http://www.cs.princeton.edu/random-approx/
Downloading URL:
Event Address*:
Princeton, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
24 August 2003
Event End Date:
26 August 2003
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2764
Number:
Month:
August
Pages:
71-82
Year*:
2003
VG Wort Pages:
24
ISBN/ISSN:
3-540-40770-7
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 Given a network with capacities and transit times on the arcs, the
quickest flow problem asks for a `flow over time' that satisfies
given demands within minimal time. In the setting of flows over
time, flow on arcs may vary over time and the transit time of an arc
is the time it takes for flow to travel through this arc. In most
real-world applications (such as, e.g., road traffic, communication
networks, production systems, etc.), transit times are not fixed but
depend on the current flow situation in the network. We consider
the model where the transit time of an arc is given as a
nondecreasing function of the rate of inflow into the arc. We prove
that the quickest $s$-$t$-flow problem is NP-hard in this setting
and give various approximation results, including an FPTAS for the
quickest multicommodity flow problem with bounded cost.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
MPG Subsubunit:
Combinatorial Optimization Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{HallLangkauSkutella2003,
AUTHOR = {Hall, Alex and Langkau, Katharina and Skutella, Martin},
 EDITOR = {Arora, Sanjeev and Jansen, Klaus and Rolim, Jose D. P. and Sahai, Amit},
 TITLE = {An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times},
 BOOKTITLE = {Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003},
 PUBLISHER = {Springer},
 YEAR = {2003},
 VOLUME = {2764},
 PAGES = {71--82},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Princeton, USA},
 MONTH = {August},
 ISBN = {3-540-40770-7},
}

Entry last modified by Sabine Krott, 06/17/2004
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Martin Skutella		Created
01/19/2004 11:04:19
Revisions
4.
3.
2.
1.
0.		Editor(s)
Sabine Krott
Christine Kiesel
Christine Kiesel
Martin Skutella
Martin Skutella		Edit Dates
17.06.2004 11:23:57
15.06.2004 14:37:37
11.06.2004 16:19:19
04.05.2004 16:09:42
19.01.2004 11:04:19