TU Berlin

Prof. Dr. Martin Skutella Publications

Page Content

to Navigation

Publications

Maximum Multicommodity Flows over Time without Intermediate Storage
Citation key GrossSkutella2012a
Author Groß, Martin and Skutella, Martin
Title of Book Algorithms – ESA 2012
Pages 539-550
Year 2012
ISBN 978-3-642-33089-6
DOI 10.1007/978-3-642-33090-2_47
Volume 7501
Editor Epstein, Leah and Ferragina, Paolo
Publisher Springer Berlin / Heidelberg
Series Lecture Notes in Computer Science
Institution TU Berlin
Abstract 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 to original publication Download Bibtex entry

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.

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe