Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances

Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, Tijn de Vos · 2025

Read Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances by Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, Tijn de Vos (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-13274.txt.

Introduction

Jan van den Brand, Hossein Gholizadeh, Yonggang Jiang, and Tijn de Vos give a parallel algorithm for the minimum cost flow problem. Their 2025 paper works on graphs with integer costs and capacities that are bounded by a polynomial.

Their randomized method uses near-linear work and about square-root depth. On fairly dense graphs it is the first to reach both goals at once, since past methods were either near-optimal in work but highly sequential, or parallel but wasteful. The result also improves special cases such as max flow, bipartite matching, shortest paths, and reachability. For theory readers, it narrows a long gap between work and depth.

Catalog record

CREATORJan van den Brand, Hossein Gholizadeh, Yonggang Jiang, Tijn de Vos
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE211 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-13274

Browse the full library · About the Tower of Babel