We present a novel simpler method for the min-cost flow problem and prove that its expected running time is bounded by Õ(m3/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 P0 = Õ(equation found). (2)We present a potential reduction algorithm that transforms initial solutions of potential P0 to ones with duality gap below 1 in Õ (P0 ・ CEF(n, m, ε)) time, where ε −1 = O(m2) and CEF(n, m, ε) denotes the running time of any algorithm that computes an ε-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-ofthe- art ε-electrical flow solver, we obtain a new simple algorithm for the min-cost flow problem running in Õ (m3/2).

A simple efficient interior point method for min-cost flow

Becker R.;
2014-01-01

Abstract

We present a novel simpler method for the min-cost flow problem and prove that its expected running time is bounded by Õ(m3/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 P0 = Õ(equation found). (2)We present a potential reduction algorithm that transforms initial solutions of potential P0 to ones with duality gap below 1 in Õ (P0 ・ CEF(n, m, ε)) time, where ε −1 = O(m2) and CEF(n, m, ε) denotes the running time of any algorithm that computes an ε-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-ofthe- art ε-electrical flow solver, we obtain a new simple algorithm for the min-cost flow problem running in Õ (m3/2).
2014
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
File in questo prodotto:
File Dimensione Formato  
3_isaac14.pdf

non disponibili

Tipologia: Versione dell'editore
Licenza: Copyright dell'editore
Dimensione 274.55 kB
Formato Adobe PDF
274.55 kB Adobe PDF   Visualizza/Apri

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/5029571
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact