2013/12/13 by Ruben Becker, Becker, Ruben, Andreas Karrenbauer +1 · 1 citation
Computer Science · Engineering · Materials Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #High voltage insulation and dielectric phenomena #Low-power high-performance VLSI design #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.1312.3905
openalex publication_date 2013/12/13 · openalex created_date 2022/10/05 · openalex updated_date 2026/07/28
We present a combinatorial method for the min-cost flow problem and prove\nthat its expected running time is bounded by O(m3/2). This matches\nthe best known bounds, which previously have only been achieved by numerical\nalgorithms or for special cases. Our contribution contains three parts that\nmight be interesting in their own right: (1) We provide a construction of an\nequivalent auxiliary network and interior primal and dual points with potential\nP0=\O(\√(m)) in linear time. (2) We present a combinatorial\npotential reduction algorithm that transforms initial solutions of potential\nP0 to ones with duality gap below 1 in O(P0\⋅\n\CEF(n,m,\ε)) time, where \ε-1=O(m2) and\n\CEF(n,m,\ε) denotes the running time of any combinatorial\nalgorithm that computes an \ε-approximate electrical flow. (3) We show\nthat solutions with duality gap less than 1 suffice to compute optimal\nintegral potentials in O(m+n\log n) time with our novel crossover procedure.\nAll in all, using a variant of a state-of-the-art \ε-electrical flow\nsolver, we obtain an algorithm for the min-cost flow problem running in nO(m3/2).\n