Kolloquiumsvortrag: Dr. Andreas Karrenbauer vom MPI

18.07.2014 von 14:15 bis 15:30

Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2

Titel: "Min-Cost Flow"



In the past years, interior point methods have conquered the domain of algorithms for network flow problems and led to a series of improvements in terms of running time. These methods are rather involved numerical algorithms using nearly-linear-time randomized algorithms for solving systems of linear equations defined by symmetric diagonally dominant matrices. We present a simpler variant of a potential reduction interior point method for the min-cost flow problem that sheds more light on combinatorial aspects of the approach. Moreover, we prove that its expected running time matches the best known bounds from literature. To this end, we first construct a an equivalent auxiliary network and initial interior primal and dual points, i.e. flows, node potentials and reduced costs. By augmenting flows along cycles or adjusting the reduced costs along the arcs over cuts, we transform the initial primal and dual interior points to ones with a duality gap less than 1. Furthermore, we present a crossover procedure that computes optimal integral node potentials in O(m+n log n) time. This is joint work with Ruben Becker.

Prof. Jansen

Diesen Termin meinem iCal-Kalender hinzufügen