Multicommodity Flows Over time with Costs

Stegantova, Evghenia

Lokale TagsFreigabegeschichteDetailsÜbersicht

Multicommodity Flows Over time with Costs

Stegantova, E. (2004). Multicommodity Flows Over time with Costs. Master Thesis, Universität des Saarlandes, Saarbrücken.

Item is Freigegeben

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:

Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-F7FE-2 Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-F7FF-F

Genre: Hochschulschrift

ausblenden:

Urheber:
Stegantova, Evghenia^{1, 2}, Autor
Skutella, Martin¹, Ratgeber

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2International Max Planck Research School, MPI for Informatics, Max Planck Society, Campus E1 4, 66123 Saarbrücken, DE, ou_1116551

Inhalt

einblenden:

ausblenden:

Schlagwörter: -

Zusammenfassung: Flows over time (dymanic flows) generalize standard network flows by introducing a new element- time. They naturally model problems where travel and transmission are not instantaneous. I this work we consider two dynamic flows problems: The Quickest multicommodity Dynamic Flow problem with Bounded Cost (QMDFP) ant The Maximal Multicommodity dynamic flow problem (MMDFP). Both problems are known to be NP-hard. In the first part we propose two methods of improving the result obtained by the efficient two-approximation algorithm proposed by Lisa Fleischer and Martin Skutella for solving the QMDFP. The Approximation algorithm constructs the temporally repeated flow using so called "static average flow". In the first method we prove that the value of the static average flow can be increased by a factor, that depends on the length of th shortest path form a source to a sink in the underlying network. Increasing the value of the static average flow allows us to save time on sending the necessary amount of flow (the given demands) from sources to sinks. The cost of the resulting temporally repeated flow remains unchanged. In the second method we porpose an algorithm that reconstructs the static average flow in the way that the length of the longest path used by the flow becomes shorter. This allows us to wait for a shorter period of time until the last sent unit of flow reaches its sink. The drawback of the reconstructing of the flow is its increase in cost. But we give a proof ot the fact that the cost increases at most by a factor of two. In the second part of the thesis we deal with MMDFP. We give an instance of the network that demonstrates that the optimal solution is not always a temporally repeated flow. But we give an easy proof of the fact that the difference between the optimal solution and the Maximal Multicommodity Temporally Repeated Flow is bounded by a constant that depends on the network and not on the given time horizon. This fact allows to approximate the optimal Maximal Multicommodity Dynamic Flow with the Maximal Muticommodity Temporally Repeated Flow for large enough time horizons.