💻 computer science

Formal Primal-Dual Algorithm Analysis

This paper outlines an ongoing initiative to develop an Isabelle/HOL framework and library for formally verifying primal-dual algorithm analysis, demonstrating its application through the formalization of both classical matching algorithms like the Hungarian Method and modern approaches such as the Adwords algorithm.

Original authors: Mohammad Abdulaziz, Thomas Ammer

Published 2026-04-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohammad Abdulaziz, Thomas Ammer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, chaotic matchmaking service. You have two groups of people: Job Seekers (on one side) and Companies (on the other). Your goal is to pair them up in a way that creates the most value, whether that means the highest total salary, the most jobs filled, or the best fit for a specific budget.

This paper is about a team of computer scientists (Mohammad Abdulaziz and Thomas Ammer) who are building a digital "proof machine" to verify that the complex math used to solve these matching problems is actually correct. They are using a special software tool called Isabelle/HOL, which acts like a super-strict math teacher that checks every single step of an argument to ensure there are no logical holes.

Here is a breakdown of their work using simple analogies:

1. The Core Idea: The "Tug-of-War" (Primal-Dual)

The paper focuses on a strategy called the Primal-Dual method. Think of this as a tug-of-war between two teams trying to find the perfect match:

Team Primal (The Matchmakers): They are trying to build a real list of pairs (a matching). They want to make the list as good as possible.
Team Dual (The Accountants): They are trying to set a "price tag" or a "budget ceiling" for the entire system. They calculate the maximum possible value the matchings could have.

The Magic Trick:
The algorithm starts with the Accountants setting a high price ceiling. The Matchmakers try to find a list of pairs that hits that price. If they can't quite reach it, the Accountants lower the ceiling slightly, and the Matchmakers try again. They keep doing this, adjusting their strategies together, until the Matchmakers find a list of pairs that exactly hits the Accountants' price ceiling.

When the two teams meet in the middle, you know you have found the absolute best solution. It's like two people walking toward each other on a tightrope; when they meet, you know they are at the exact center.

2. The Three Algorithms They Verified

The authors didn't just talk about theory; they built formal proofs for three specific types of "matchmaking" algorithms:

A. The "Naive" Approach (The Slow but Steady Worker)

The Analogy: Imagine trying to fill a room with people by checking every single door one by one. It works, but it's slow.
The Math: This is a basic algorithm that adjusts the "prices" (potentials) of the people until a perfect match is found.
The Verification: The authors proved that this method always works and eventually stops, provided the prices are set up correctly. It's the "Hello World" of their formal library.

B. The Hungarian Method (The Efficient Optimizer)

The Analogy: This is like a professional matchmaker who doesn't just check doors randomly. They use a map and a compass to find the shortest path to a solution.
The Math: This is the famous "Hungarian Algorithm" used to find the cheapest way to assign tasks to workers. It's much faster than the naive approach.
The Verification: Proving this is hard because the algorithm is complex. The authors had to prove that the "map" (the data structures) never gets corrupted and that the algorithm always finds the cheapest possible assignment. They showed that their code is mathematically guaranteed to be correct.

C. The "Adwords" & "Ranking" Algorithms (The Online Gamblers)

The Analogy: Imagine a live auction where bidders arrive one by one, and you have to decide immediately whether to accept their bid or let them go forever. You don't know who is coming next. This is how Google AdWords works (matching ads to search queries in real-time).
The Math: These are "Online Algorithms." They have to make decisions without knowing the future. The proof here is tricky because it involves randomness (like shuffling a deck of cards).
The Verification: The authors used a clever trick. Instead of trying to track every possible shuffle of the deck, they treated the "shuffling" as a continuous flow of numbers (like a smooth river). This allowed them to use standard math to prove that, on average, these online algorithms are incredibly good at their job (specifically, they are at least 63% as good as the perfect solution).

3. Why Does This Matter?

You might ask, "Why do we need a computer to check the math for these algorithms?"

Trust: In the real world, these algorithms decide who gets a loan, which ads you see, or how traffic lights are timed. If the math is slightly wrong, the system could fail or be unfair.
Simplicity: The authors found that using the "Primal-Dual" (Tug-of-War) method makes the proofs shorter and easier to read than older, more complicated combinatorial proofs. It's like replacing a 100-page manual with a clear, 10-page flowchart.
The Future: They are building a "library" of these verified proofs. In the future, software engineers can just grab a "verified matching algorithm" from this library, knowing it's been checked by the super-strict math teacher, rather than writing their own from scratch and hoping for the best.

Summary

In short, this paper is about building a fortress of certainty around the algorithms that run our digital economy. By using a "Primal-Dual" strategy (balancing a solution against a budget), the authors have proven that some of the most important matching algorithms in the world are mathematically sound, efficient, and ready for the real world. They turned complex, scary math into a verified, reliable tool.

1. Problem Statement

The paper addresses the challenge of formalizing the primal-dual (PD) paradigm for algorithm analysis within the Isabelle/HOL proof assistant. While the primal-dual method is a cornerstone of combinatorial optimization (used for exact algorithms like the Hungarian Method and approximation algorithms like Adwords), its formal verification has historically been difficult.

The Gap: Existing formalizations often rely on complex combinatorial arguments (e.g., case analyses, augmenting paths) which are verbose and hard to verify. There is a lack of a unified library that captures the algebraic and matrix-based reasoning inherent to primal-dual proofs.
The Goal: To build a framework and library in Isabelle/HOL that formalizes primal-dual arguments, covering both classical offline algorithms (e.g., Maximum Weight Bipartite Matching) and modern online algorithms (e.g., Adwords, RANKING).

2. Methodology

The authors employ a structured approach to formalization, focusing on the translation of graph-theoretic problems into linear programming (LP) frameworks.

Mathematical Core (LP & Duality):
- The optimization problems are encoded as Linear Programs (LPs).
- Primal: Represents the matching (e.g., $max \{c^T x \mid Ax \le b, x \ge 0\}$ ).
- Dual: Represents vertex potentials (e.g., $min \{b^T y \mid A^T y \ge c, y \ge 0\}$ ).
- Key Principles: The formalization relies heavily on Weak Duality (WD) and Complementary Slackness (CS). The algorithm maintains a feasible dual solution and iteratively adjusts it to satisfy CS with a primal candidate until the primal becomes feasible (optimal).
- Representation: The authors reuse existing matrix formalizations in Isabelle/HOL to handle the algebraic core, connecting graph concepts (matchings, potentials) to matrix operations via translation lemmas.
Formalization Strategy:
- Deterministic Algorithms: Modeled as functional programs (recursive functions for loops, records for state). Correctness is proven via invariants (properties of the initial state preserved by loop iterations).
- Probabilistic Algorithms: Modeled using the Giry monad formalization in Isabelle/HOL to reason about expectations and randomization.
- Stepwise Refinement: Algorithms are decomposed into subprocedures using Isabelle's locales, which fix mathematical entities and assume properties, allowing for modular proofs.

3. Key Contributions & Results

The paper presents formal analyses of three distinct categories of algorithms, totaling approximately 14,000 lines of code.

A. Naive Maximum Weight Bipartite Matching

Algorithm: A basic primal-dual algorithm that maintains a feasible potential $\pi$ and searches for a "tight" matching (edges where $\pi(u) + \pi(v) = w(e)$ ).
Mechanism: If a tight matching covering all non-zero potential vertices is not found, it performs a Primal-Dual Adjustment (PDA): it identifies a set of vertices $X$ violating Hall's condition and adjusts potentials by a step size $\epsilon$ to reduce the dual objective while maintaining feasibility.
Result: Proved that if the algorithm terminates, it returns a maximum weight matching. Termination is guaranteed for integer weights.

B. The Hungarian Method (HM)

Context: The naive approach can be exponential. The HM improves this by combining PDAs with augmenting path searches to guarantee polynomial time.
Formalization:
- Focuses on minimum weight perfect matchings (reducible from max-weight via graph extension).
- Implements a PathSearch procedure using alternating forests and priority search trees to find augmenting paths efficiently.
- Complexity: Verified an $O(n \cdot (n + m) \cdot \log n)$ implementation, which is optimal for purely functional implementations.
- Invariants: Maintained 8 specific invariants during the path search and potential updates to ensure correctness.

C. Online Matching (RANKING & Adwords)

Challenge: Online algorithms involve randomization and irrevocable decisions, making standard combinatorial proofs (like those by Karp et al.) extremely complex and difficult to formalize.
Innovation: The authors formalize a simplified Primal-Dual analysis for online algorithms.
- Instead of complex combinatorial arguments, they define a dual LP where potentials depend on random priorities ( $Y_i \in [0, 1]$ ) assigned to offline vertices.
- They prove the competitive ratio by relating the expected value of the primal (matching size) to the expected value of the dual.
Results:
- RANKING Algorithm: Formalized the proof that the competitive ratio is at least $1 - 1/e$ . The PD proof is significantly shorter (less than half the length) and simpler than previous combinatorial formalizations.
- Adwords Algorithm: Extended the framework to formalize the analysis of the Adwords algorithm (online b-matching), demonstrating the generality of the approach.

4. Significance

Simplification of Proofs: The paper demonstrates that algebraic/linear programming reasoning (PD arguments) is often simpler, shorter, and more "textbook-style" than complex combinatorial proofs. For example, the formalized PD proof for RANKING is drastically less complex than the formalized combinatorial proof.
Unified Framework: It establishes a reusable library for primal-dual reasoning. Once the core LP duality and CS lemmas are formalized, they can be applied to various algorithms (offline and online) with minimal adaptation.
Bridging Theory and Practice: The work covers both practical, executable algorithms (Hungarian Method with verified data structures) and theoretical models (online markets), showing the versatility of the formalization.
Future Impact: The authors identify the formalization of approximation algorithms (e.g., MaxSAT, Set Cover, Steiner Trees) as the next major milestone, aiming to cover the majority of applications of the primal-dual paradigm in theoretical computer science.

In summary, this work provides a robust, verified foundation for the primal-dual method in Isabelle/HOL, proving that this powerful algorithmic paradigm can be rigorously verified with greater ease and clarity than traditional combinatorial approaches.