Paper Info
Title
A Simple Efficient Interior Point Method for Min-Cost Flow.
Abstract
We present a novel simpler method for the min-cost flow problem and prove that its expected running time is bounded by (O) over tilde (m(3/2)). This matches the best known bounds, which have previously been achieved only by far more complex algorithms or by algorithms for special cases. Our contribution contains three algorithmic parts that are interesting in their own right: (1) We provide a linear time construction of an equivalent auxiliary network and interior primal and dual points, i.e. flows, node potentials and slacks, with potential P-0 = (O) over tilde(root m). (2) We present a potential reduction algorithm that transforms initial solutions of potential P-0 to ones with duality gap below 1 in (O) over tilde (P-0 center dot CEF(n, m, epsilon)) time, where epsilon(-1) = O(m(2)) and CEF(n, m, epsilon) denotes the running time of any algorithm that computes an epsilon-approximate electrical flow. (3) We show that, taking solutions with duality gap less than 1 as input, one can compute optimal integral node potentials in O(m + n log n) time with our novel crossover procedure. Altogether, using a variant of a state-of-the-art e-electrical flow solver, we obtain a new simple algorithm for the min-cost flow problem running in (O) over tilde (m(3/2)).
Year
DOI
Venue
2014
10.1007/978-3-319-13075-0_59
ALGORITHMS AND COMPUTATION, ISAAC 2014
DocType
Volume
ISSN
Conference
8889
0302-9743
Citations 
PageRank 
References 
0
0.34
12
Authors
2
Name
Order
Citations
PageRank
Ruben Becker1315.27
Andreas Karrenbauer213320.21