TU Berlin

Prof. Dr. Martin SkutellaVeröffentlichungen

Inhalt des Dokuments

zur Navigation


Maximum Multicommodity Flows over Time without Intermediate Storage
Zitatschlüssel GrossSkutella2012a
Autor Groß, Martin and Skutella, Martin
Buchtitel Algorithms – ESA 2012
Seiten 539-550
Jahr 2012
ISBN 978-3-642-33089-6
DOI 10.1007/978-3-642-33090-2_47
Jahrgang 7501
Herausgeber Epstein, Leah and Ferragina, Paolo
Verlag Springer Berlin / Heidelberg
Serie Lecture Notes in Computer Science
Institution TU Berlin
Zusammenfassung 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).
Link zur Originalpublikation Download Bibtex Eintrag

Copyright notice

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.



Schnellnavigation zur Seite über Nummerneingabe