Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem
Speaker:Ruben Becker
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 8 December 2015
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
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
Name(s):Ruben Becker
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created by:Ruben Becker, 11/23/2015 07:41 PMLast modified by:Uwe Brahm/MPII/DE, 11/24/2016 04:13 PM
  • Ruben Becker, 11/23/2015 07:41 PM -- Created document.