Skip to main content

2012 | OriginalPaper | Buchkapitel

Maximum Multicommodity Flows over Time without Intermediate Storage

verfasst von : Martin Groß, Martin Skutella

Erschienen in: Algorithms – ESA 2012

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Flows over time generalize classical “static” network flows by introducing a temporal dimension. They can thus be used to model non-instantaneous travel times for flow and variation of flow values over time, both of which are crucial characteristics in many real-world routing problems. There exist two different models of flows over time with respect to flow conservation: one where flow might be stored temporarily at intermediate nodes and a stricter model where flow entering an intermediate node must instantaneously progress to the next arc. While the first model is in general easier to handle, the second model is often more realistic since in applications like, e.g., road traffic, storage of flow at intermediate nodes is undesired or even prohibited. The main contribution of this paper is a fully polynomial time approximation scheme (FPTAS) for (min-cost) multi-commodity flows over time without intermediate storage. This improves upon the best previously known (2 + 

ε

)-approximation algorithm presented 10 years ago by Fleischer and Skutella (IPCO 2002).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Metadaten
Titel
Maximum Multicommodity Flows over Time without Intermediate Storage
verfasst von
Martin Groß
Martin Skutella
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/978-3-642-33090-2_47