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

Baumann, Nadine
Köhler, Ekkehard

dblp
dblp

Not MPG Author(s):

Köhler, Ekkehard

Editor(s):

Fiala, Jiri
Koubek, Vaclav
Kratochvil, Jan

dblp
dblp
dblp

Not MPII Editor(s):

Fiala, Jiri
Koubek, Vaclav
Kratochvil, Jan

BibTeX cite key*:

Baumann2004

Title, Booktitle

Title*:

Approximating Earliest Arrival Flows with Flow-Dependent Transit Times

Booktitle*:

Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004

Event, URLs

URL of the conference:

http://mfcs.mff.cuni.cz/

URL for downloading the paper:


Event Address*:

Prague, Czech Republic

Language:

English

Event Date*
(no longer used):


Organization:

Mathematical Foundations of Computer Science (MFCS)

Event Start Date:

22 August 2004

Event End Date:

27 August 2004

Publisher

Name*:

Springer

URL:

http://www.springer-sbm.com/

Address*:

Berlin, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

3153

Number:


Month:

August

Pages:

599-610

Year*:

2004

VG Wort Pages:

11

ISBN/ISSN:

3-540-22823-3

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

For the earliest arrival flow problem one is given a network $G=(V,
A)$ with capacities $u(a)$ and transit times $\tau(a)$ on its arcs $a
\in A$, together with a source and a sink vertex $s, t \in V$. The
objective is to send flow from $s$ to $t$ that moves through the
network over time, such that for each point in time $\theta \in
[0,T)$ the maximum possible amount of flow reaches $t$. If, for
each $\theta \in [0,T)$ this flow is a maximum flow for time horizon
$\theta$, then it is called \emph{earliest arrival flow}. In
practical applications a higher congestion of an arc in the network
often implies a considerable increase in transit time. Therefore,
in this paper we study the earliest arrival problem for the case
that the transit time of each arc in the network at each time
$\theta$ depends on the flow on this particular arc at that time
$\theta$.

For constant transit times it has been shown by Gale that earliest
arrival flows exist for any network. We give examples, showing that
this is no longer true for flow-dependent transit times. For that
reason we define an optimization version of this problem where the
objective is to find flows that are almost earliest arrival flows.
In particular, we are interested in flows that, for each $\theta \in
[0,T)$, need only $\alpha$-times longer to send the maximum flow to
the sink. We give both constant lower and upper bounds on $\alpha$;
furthermore, we present a constant factor approximation algorithm
for this problem. Finally, we give some computational results to
show the practicability of the designed approximation algorithm.

Keywords:

approximation algorithms, dynamic network flows



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Baumann2004,
AUTHOR = {Baumann, Nadine and K{\"o}hler, Ekkehard},
EDITOR = {Fiala, Jiri and Koubek, Vaclav and Kratochvil, Jan},
TITLE = {Approximating Earliest Arrival Flows with Flow-Dependent Transit Times},
BOOKTITLE = {Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004},
PUBLISHER = {Springer},
YEAR = {2004},
ORGANIZATION = {Mathematical Foundations of Computer Science (MFCS)},
VOLUME = {3153},
PAGES = {599--610},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Prague, Czech Republic},
MONTH = {August},
ISBN = {3-540-22823-3},
}


Entry last modified by Uwe Brahm, 01/20/2009
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)
Nadine Baumann
Created
03/08/2005 01:37:52 PM
Revisions
3.
2.
1.
0.
Editor(s)
Uwe Brahm
Christine Kiesel
Christine Kiesel
Nadine Baumann
Edit Dates
01/20/2009 07:10:55 PM
26.04.2005 00:09:58
26.04.2005 00:09:12
03/08/2005 01:37:52 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section