Skip to content
Log in
Sponsored AI Networking Cookbook: Practical recipes for AI-assisted network automation and development AI Networking Cookbook: Practical recipes for AI-assisted network automation and development
Conference

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

Rasmus Kyng Aurelio L. Sulser
2026 · International Colloquium on Automata, Languages and Programming · pp. 136:1-136:22 · 0 citations · 28 references
Computer Science

TL;DR

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.

DOI Semantic Scholar
View source

Similar papers

Preprint Aug 2026

Fixed-Threshold Peeling in Sublinear MPC: Round-Approximation Tradeoffs and Applications

This is the first $O(1)$-approximate algorithm for densest subgraph to break the $\Theta(\sqrt{\lg n})$ round-complexity barrier in the sub-linear MPC model and achieves the following round-approximation tradeoffs.

Slobodan Mitrović, Theodore Pan, Wen-Horng Sheu · 0 citations
#machine learning Preprint Aug 2026

Adversarial Resilience of Poisson-Process Submodular Maximization over Matroids: From Robust Offline Optimization to Full-Bandit Learning

The main result is an adversarial resilience theorem for the Spiteful Greedy Swap Poisson Process (SGS-Poisson): without modifying its Poisson intensity, single-element exchange rule, or spiteful drop step, the algorithm retains limiting approximation factors for non-monotone objectives and $1-1/e for monotone objectives.

Vaneet Aggarwal · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.