Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.cs.princeton.edu/random-approx/

URL for downloading the paper:


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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 AM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section