3 papers
cs.LO2026
Formal Primal-Dual Algorithm Analysis
Mohammad Abdulaziz, Thomas Ammer, Christoph Madlener
We present an ongoing effort to build a framework and a library in Isabelle/HOL for formalising primal-dual arguments for the analysis of algorithms. We discuss a number of example…
cs.LO2026
A Formal Analysis of Capacity Scaling Algorithms for Minimum-Cost Flows
Mohammad Abdulaziz, Thomas Ammer
We present formalisations of the correctness of executable algorithms to solve minimum-cost flow problems in Isabelle/HOL. Two of the algorithms are based on the technique of scali…
cs.LO2025
A Formal Analysis of Algorithms for Matroids and Greedoids
Mohammad Abdulaziz, Thomas Ammer, Shriya Meenakshisundaram +1
We present a formal analysis, in Isabelle/HOL, of optimisation algorithms for matroids, which are useful generalisations of combinatorial structures that occur in optimisation, and…