hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS,Mathematics, Numerical Analysis, math.NA,Mathematics, Optimization and Control, math.OC
Abstract:
We present an interior point method for the min-cost flow problem that uses
arc contractions and deletions to steer clear from the boundary of the polytope
when path-following methods come too close. We obtain a randomized algorithm
running in expected $\tilde O( m^{3/2} )$ time that only visits integer lattice
points in the vicinity of the central path of the polytope. This enables us to
use integer arithmetic like classical combinatorial algorithms typically do. We
provide explicit bounds on the size of the numbers that appear during all
computations. By presenting an integer arithmetic interior point algorithm we
avoid the tediousness of floating point error analysis and achieve a method
that is guaranteed to be free of any numerical issues. We thereby eliminate one
of the drawbacks of numerical methods in contrast to combinatorial min-cost
flow algorithms that still yield the most efficient implementations in
practice, despite their inferior worst-case time complexity.
