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

Fleischer, Lisa
Skutella, Martin

dblp
dblp

Not MPG Author(s):

Fleischer, Lisa

Editor(s):





BibTeX cite key*:

FleischerSkutella2003

Title, Booktitle

Title*:

Minimum Cost Flows Over Time without Intermediate Storage

Booktitle*:

Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)

Event, URLs

URL of the conference:

http://www.siam.org/meetings/da03/

URL for downloading the paper:


Event Address*:

Baltimore, USA

Language:

English

Event Date*
(no longer used):


Organization:

Society of Industrial and Applied Mathematics

Event Start Date:

12 January 2003

Event End Date:

14 January 2003

Publisher

Name*:

ACM

URL:

http://www.siam.org/

Address*:

New York, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:

January

Pages:

66-75

Year*:

2003

VG Wort Pages:

24

ISBN/ISSN:

0-89871-538-5

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Flows over time (also called dynamic flows)
generalize standard network flows by introducing
an element of time. They naturally model problems where
travel and transmission are not instantaneous. Solving these problems
raises issues that do not arise in standard network flows.
One issue is the question of storage of flow at intermediate nodes.
In most applications
(such as, e.g., traffic routing, evacuation planning,
telecommunications etc.), intermediate storage is limited, undesired,
or prohibited.

The minimum cost flow over time problem is NP-hard. In this paper we
1)~prove that the minimum cost flow over time never requires storage;
2)~provide the first approximation scheme for minimum cost flows over
time that does not require storage; 3)~provide the first approximation
scheme for minimum cost flows over time that meets hard cost
constraints, while approximating only makespan.

Our approach is based on a condensed variant of time-expanded
networks. It also yields fast approximation schemes with simple
solutions for the quickest multicommodity flow problem.

Finally, using completely different techniques, we describe a very
simple capacity scaling FPAS for the minimum cost flow over time
problem when costs are proportional to transit times.
The algorithm builds upon our observation about the
structure of optimal solutions to this problem:
they are universally quickest flows. Again, the FPAS
does not use intermediate node storage.
In contrast to the preceding algorithms that use a
time-expanded network, this FPAS runs directly on the original
network.



Download
Access Level:

Intranet

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{FleischerSkutella2003,
AUTHOR = {Fleischer, Lisa and Skutella, Martin},
TITLE = {Minimum Cost Flows Over Time without Intermediate Storage},
BOOKTITLE = {Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)},
PUBLISHER = {ACM},
YEAR = {2003},
ORGANIZATION = {Society of Industrial and Applied Mathematics},
PAGES = {66--75},
ADDRESS = {Baltimore, USA},
MONTH = {January},
ISBN = {0-89871-538-5},
}


Entry last modified by Christine Kiesel, 08/02/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 01:00:56 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Edit Dates
15.06.2004 15:08:40
15.06.2004 15:08:22
14.06.2004 08:35:35
14.06.2004 08:34:49
04.05.2004 16:10:35