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

CREATORMohammad Abdulaziz \ourflowspaperorcid 0000-0002-8244-518X, Thomas Ammer \ourflowspaperorcid 0009-0001-5301-4620
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE159 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-03701

Browse the full library · About the Tower of Babel