A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem ALENEX 2016
A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem
Ruben Becker1
Maximilian Fickert1
Andreas Karrenbauer1
1 MPI for Informatics, Germany
A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem
Ruben Becker1 Maximilian Fickert1 Andreas Karrenbauer1
1 MPI for Informatics, Germany
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 outper- forms 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 vec- tor 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.
Materials for Download
|
Addditional Materials
- Source Code: dual ascent algorithm implemented in C++, version 1, used for the ALENEX paper and version 2:
source code in a gzipped tar archive. source code in a gzipped tar archive. - Min-cost flow instances:
netgen_8,
netgen_sr,
goto_8,
road_paths,
road_flow,
feas_grid.
All but the last graph classes are downloaded from https://lemon.cs.elte.hu/trac/lemon
Citation
Ruben Becker, Maximilian Fickert, Andreas Karrenbauer
A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem
2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and
Experiments (ALENEX), chapter 12, pages 151 - 159.
@inbook{BFK2016,
author = {Ruben Becker and Maximilian Fickert and Andreas Karrenbauer},
title = {A Novel Dual Ascent Algorithm for Solving the Min-Cost Flow Problem},
booktitle = {2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX)},
chapter = {12},
pages = {151-159},
doi = {10.1137/1.9781611974317.13},
URL = {http://epubs.siam.org/doi/abs/10.1137/1.9781611974317.13},
eprint = {http://epubs.siam.org/doi/pdf/10.1137/1.9781611974317.13}
}