English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Approximating Earliest Arrival Flows with Flow-Dependent Transit Times

Baumann, N., & Köhler, E. (2004). Approximating Earliest Arrival Flows with Flow-Dependent Transit Times. In Mathematical foundations of computer science 2004: 29th International Symposium, MFCS 2004 (pp. 599-610). Berlin, Germany: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Baumann, Nadine1, Author           
Köhler, Ekkehard, Author
Fiala, Jiri, Editor
Koubek, Vaclav, Editor
Kratochvil, Jan, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2005-04-262004
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 231172
Other: Local-ID: C1256428004B93B8-250FFD1F2B007FD0C1256FBE004562BE-Baumann2004
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Prague, Czech Republic
Start-/End Date: 2004-08-22

Legal Case

show

Project information

show

Source 1

show
hide
Title: Mathematical foundations of computer science 2004 : 29th International Symposium, MFCS 2004
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 599 - 610 Identifier: ISBN: 3-540-22823-3

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 3153 Sequence Number: - Start / End Page: - Identifier: -