非表示:
キーワード:
-
要旨:
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.
