MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem

Ruben Becker
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI  
AG Audience
English

Date, Time and Location

Tuesday, 8 December 2015
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

We present a novel algorithm for the min-cost flow problem that is competitive with recent third-party implementations of well-known algorithms for this problem and even outperforms them on certain realistic instances. We formally prove correctness of our algorithm and show that the worst-case running time is in O(||b||_1(m + n log n)) where b is the vector of demands. Combined with standard scaling techniques, this pseudo-polynomial bound can be made polynomial in a straightforward way. Furthermore, we evaluate our approach experimentally. Our empirical findings indeed suggest that the running time does not significantly depend on the costs and that a linear dependence on ||b||_1 is overly pessimistic.


Co-authors Maximilan Fickert and Andreas Karrenbauer

Contact

Ruben Becker
--email hidden
passcode not visible
logged in users only

Ruben Becker, 11/23/2015 19:41 -- Created document.