A Formal Analysis of Capacity Scaling Algorithms for Minimum-Cost Flows
Mohammad Abdulaziz \ourflowspaperorcid 0000-0002-8244-518X, Thomas Ammer \ourflowspaperorcid 0009-0001-5301-4620 · 2026
Read A Formal Analysis of Capacity Scaling Algorithms for Minimum-Cost Flows by Mohammad Abdulaziz \ourflowspaperorcid 0000-0002-8244-518X, Thomas Ammer \ourflowspaperorcid 0009-0001-5301-4620 (2026) 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-2602-03701.txt.
Description
Mohammad Abdulaziz and Thomas Ammer verify minimum-cost flow algorithms inside the Isabelle/HOL proof assistant in a 2026 paper. Minimum-cost flow routes goods through a network at least total cost, and fast algorithms for it usually rest on pen-and-paper proofs. These authors formalize the correctness of executable versions, leaving nothing to trust.
Two of the algorithms use capacity scaling, including Orlin's algorithm, which has the fastest known running time; its worst-case argument is formalized too. Stepwise refinement turns the proofs into code that actually runs, now part of a reusable graph-algorithms library. A verified reduction extends the results to the general problem. The work also produced sharper proofs and theorem statements than existing expositions.
Catalog record
| CREATOR | Mohammad Abdulaziz \ourflowspaperorcid 0000-0002-8244-518X, Thomas Ammer \ourflowspaperorcid 0009-0001-5301-4620 |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 159 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-03701