A Simple and Efficient Interior Point Method for Min-Cost Flow
Staff - Faculty of Informatics
Start date: 14 April 2015
End date: 15 April 2015
The Faculty of Informatics is pleased to announce a seminar given by Andreas Karrenbauer
DATE: Tuesday, April 14th 2015
PLACE: USI Lugano Campus, room SI-004, Informatics building (Via G. Buffi 13)
TIME: 13.30
ABSTRACT:
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 worst case running times. 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. 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.
BIO:
Andreas Karrenbauer is a Senior Researcher at the Max Planck Institute for Informatics in Saarbuecken, Germany. He obtained his PhD from Saarland University, Germany, in 2007. He worked as a Postdoc at EPFL before moving to the University of Konstanz in 2010 to become a Research Fellow and a research group leader. Since 2013, he is the head of the Discrete Optimization group at the Max Planck Center for Visual Computing and Communication.
HOST: Prof. Rolf Krause
