Aurelio L. Sulser

Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow

This work presents the first polylog-depth, nearly-linear-work parallel algorithm that achieves a (1 + ε )- bicriteria approximation guarantee for undirected minimum-cost flow on expanders and suggests a promising route toward e O ( m/ε ) work and e O (1 /ε ) depth algorithms for approximate undirected minimum-cost flow on general graphs.