Paper Info
Title
A Combinatorial $\tilde{O}(m^{3/2})$-time Algorithm for the Min-Cost Flow Problem.
Abstract
We present a combinatorial method for the min-cost flow problem and prove that its expected running time is bounded by $\tilde O(m^{3/2})$. This matches the best known bounds, which previously have only been achieved by numerical algorithms or for special cases. Our contribution contains three parts that might be interesting in their own right: (1) We provide a construction of an equivalent auxiliary network and interior primal and dual points with potential $P_0=\tilde{O}(\sqrt{m})$ in linear time. (2) We present a combinatorial potential reduction algorithm that transforms initial solutions of potential $P_0$ to ones with duality gap below $1$ in $\tilde O(P_0\cdot \mbox{CEF}(n,m,\epsilon))$ time, where $\epsilon^{-1}=O(m^2)$ and $\mbox{CEF}(n,m,\epsilon)$ denotes the running time of any combinatorial algorithm that computes an $\epsilon$-approximate electrical flow. (3) We show that solutions with duality gap less than $1$ suffice to compute optimal integral potentials in $O(m+n\log n)$ time with our novel crossover procedure. All in all, using a variant of a state-of-the-art $\epsilon$-electrical flow solver, we obtain an algorithm for the min-cost flow problem running in $\tilde O(m^{3/2})$.
Year
Venue
Field
2013
CoRR
Discrete mathematics,Binary logarithm,Duality gap,Combinatorics,Crossover,Combinatorial method,Algorithm,Solver,Time complexity,Minimum-cost flow problem,Mathematics,Bounded function
DocType
Volume
Citations 
Journal
abs/1312.3905
1
PageRank 
References 
Authors
0.35
7
2
Name
Order
Citations
PageRank
Ruben Becker1315.27
Andreas Karrenbauer213320.21