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: Goto entry point

 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:

 (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},
MONTH = {August},
ISBN = {3-540-22823-3},
}