Flows over time and submodular function minimization
Miriam Schlöter · DepositOnce · 2018
Many parts of our daily routine that we expect to "just work" rely on certain optimization processes that most of the time take place in a network. Ranging from streets, railroads or power networks to the telecommunications network used by the Internet and the networks induced by social networks: the list of structures that can be modeled as a network goes on and on and optimization processes on these networks are vital throughout our daily life. In many network optimization problems the goal is to transport a commodity through the network in an efficient manner, e.g., people, objects, or more abstract commodities like the information you receive over a social network, or the movie you want to stream. Often a huge amount of the same commodity needs to be transported at once, like the large number of newspapers that are delivered each morning, the amount of data that travels through the communications network when you stream the latest episode of your favorite TV show, or the electricity that is needed to power the local hospital. Such transportation problems gave rise to the development of static network flows more than 90 years ago. For many optimization problems on networks it is essential that a certain deadline is met and also that it takes time for a commodity to travel along an arc of the network, e.g. a street or a power cable. Such properties are not incorporated in the classical static network model. Here dynamic networks and flows over time come into play which are capable of modeling temporal aspects of transportation problems. In this thesis we study such network flows over time. In particular we concentrate on two classical flow over time problems that are especially useful in the context of evacuation planning. For both problems we give new and more efficient algorithms for solving them that exploit connections between the specific flow over time problem and suitably chosen submodular functions. When evacuating people from a dangerous situation the main objective that comes to mind immediately is to save all people as quickly as possible. This property is incorporated by quickest transshipments, which are the first class of flows over time that we concentrate on throughout this thesis. In the quickest transshipment problem we are given a dynamic network with sources and sinks, and supplies and demands, respectively, and the goal is to find a flow over time that fulfills these supplies and demands as quickly as possible. The first main result in this thesis is a new strongly polynomial time algorithm for the quickest transshipment problem that significantly improves upon the so far best known algorithm for this problem, the algorithm by Hoppe and Tardos. Our algorithm exploits a connection between quickest transshipments and certain submodular functions and we use this connection to show that a solution to the quickest transshipment problem can essentially be found by only one parametric submodular function minimization. With our algorithm we achieve the first improvement for solving the quickest transshipment problem in more than 20 years. When evacuating people using quickest transshipments, all people are rescued as quickly as possible. However, in many dangerous situation it is not clear, when the actual disaster will occur, e.g. after a bomb threatening it is usually not known if or when the bomb will detonate. In such a situation evacuating people using quickest transshipments is not a good idea as it is not clear whether it is even possible to evacuate all people. Better suited for such situations are earliest arrival transshipments, which additionally have the property that as much flow as possible has arrived at the sinks at every point in time simultaneously. Thus, even if it is not possible to save all endangered people, when using earliest arrival transshipments, it is at least ensured that as many people as possible are rescued. However, the problem with earliest arrival transshipments is that they do not always exist. Furthermore, it is unlikely that polynomial time algorithms for earliest arrival transshipment problems do exist as it was recently shown that computing them is NP-hard. One special case of dynamic networks in which earliest arrival transshipments do exist in general, are dynamic networks with only a single sink. For this special class of networks we present the first polynomial space algorithm for solving earliest arrival transshipment problems. In particular our algorithm does not require any form of expansion of the original dynamic network. This solves a problem which has been open for more than ten years. In dynamic networks with multiple sinks, earliest arrival transshipments do not exist in general and so far not much research has been put into developing efficient algorithms for computing earliest arrival transshipments in multiple sink networks (in case of existence). We present the first polynomial space algorithm that checks whether an earliest arrival transshipment does exist and computes it in case of existence for the special case of earliest arrival transshipment problems in dynamic networks with multiple sinks and a single source, and tight problems in general networks.