Randomized methods in network optimization

Network flows are a fundamental modelling tool in applications of Discrete Mathematics such as the ones in the Application Area B ("Traffic and communication networks") of the DFG Research Center Matheon. In this project, we investigated the role that randomness can play both within the design as well as within the performance analyses of algorithms for computing network flows. Our goals with respect to the design of algorithms included randomized algorithms for the Min-Cost-Flow problem, the identification of polynomial time randomized pivot rules for the simplex-algorithm for the Max-Flow problem, and the search for randomized approximation algorithms for hard problems within the field of "flows over time". Our main focus in studying the role of randomness in the analyses of network flow algorithms was on the "smoothed analysis" introduced by Spielman and Teng (2001).