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).


  • Stefan Heinz, Volker Kaibel, Matthias Peinhardt, Jörg Rambau, Andreas Tuchscherer. Relative policy evaluation in constant–degree Markov Decision Problems. Technical Report , Konrad–Zuse–Zentrum Berlin, 2005.
  • Volker Kaibel, Matthias Peinhardt. On the Bottleneck Shortest Path Problem. Technical Report , Konrad–Zuse–Zentrum Berlin, 2005.
  • Bernd Gärtner, Volker Kaibel. Two New Bounds for the Random–Edge Simplex Algorithm. Technical Report 216, DFG Research Center Matheon, 2005.
  • Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler. The Simplex Algorithm in Dimension Three. SIAM J. Comput., 34(2):475–497, 2005.