2026-07-26T08:01:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26525 2026-07-01T07:16:14Z ddc:004 open_access

Back in the Saddle: Toward Parallel Approximate Minimum-Cost Flow Kyng, Rasmus Sulser, Aurelio L. Approximate Min-Cost-Flow Parallel Area-Convexity Expanders 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 ‖f‖_∞ ≤ 1+ε and ‖f‖_1 ≤ (1+ε)min_{Bg = d, ‖g‖_∞ ≤ 1}}‖g‖_1. 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 [Sherman, 2017]), 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rasmus Kyng and Aurelio L. Sulser 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.136 urn:nbn:de:0030-drops-265255 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.136 eng https://creativecommons.org/licenses/by/4.0/legalcode