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

We present the first polylog-depth, nearly-linear-work parallel algorithm that achieves a (1 + ε)bicriteria approximation guarantee for undirected minimum-cost flow on expanders. Fix an undirected graph G = (V, E) with unit capacities, unit lengths, and conductance ϕ. For any feasible demand vector d and any ε ∈ (0, 1) we compute, in Õ(|E|/εϕ) work and Õ(1/εϕ) depth, a flow f that routes d exactly while satisfying (Formula presented) This bicriteria guarantee simultaneously controls congestion and total cost, strengthens the previously studied notion of throughput error, and matches the best known ε-dependence for parallel maximum flow/transshipment on general graphs. Our main contribution is a new saddle-point optimization method for mixed ℓ∞-ℓ1 optimization. Concretely, we (i) formulate a two-term regression capturing minimum-cost flow as a saddle-point problem that couples ℓ∞ and ℓ1 terms, (ii) construct a small-magnitude area-convex regularizer tailored to the resulting primal-dual domain (building on Sherman's area-convexity framework [23]), and (iii) implement efficient δ-approximate maximization/minimization oracles so that Sherman's extragradient iteration yields low iteration-count convergence. Beyond the concrete expander result, our mixed ℓ∞-ℓ1 optimization toolkit appears broadly applicable and suggests a promising route toward Õ(m/ε) work and Õ(1/ε) depth algorithms for approximate undirected minimum-cost flow on general graphs.