Formal Primal-Dual Algorithm Analysis

Mohammad Abdulaziz, Thomas Ammer · 2026

Read Formal Primal-Dual Algorithm Analysis by Mohammad Abdulaziz, Thomas Ammer (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-2604-20807.txt.

Introduction

Abdulaziz, Ammer, and Madlener are building Isabelle/HOL tools for formalising primal-dual arguments: a framework plus a library. They discuss example formalisations from matching theory, covering classic methods like the Hungarian Method, widely seen as the first primal-dual method. They also cover modern methods like the Adwords method, which models giving search queries to advertisers in search engines.

Catalog record

CREATORMohammad Abdulaziz, Thomas Ammer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29990
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20807

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Formal Primal-Dual Algorithm Analysis Mohammad Abdulaziz, Thomas Ammer Abstract 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 formalisations from the theory of matching algorithms, covering classical algorithms like the Hungarian Method, widely considered the first primal-dual algorithm, and modern algorithms like the Adwords algorithm, which models the assignment of search queries to advertisers in the context of search engines. King’s College London, United Kingdom and https://mabdula.github.io/ [email protected]://orcid.org/0000-0002-8244-518X King’s College London, United Kingdom and https://toamme.github.io/ [email protected]://orcid.org/0009-0001-5301-4620 \lstset xleftmargin=0pt, xrightmargin=0pt, frame=single, rulecolor= , basicstyle= , keywordstyle= , morekeywords=locale,record,definition,abbreviation,primrec,function,theorem,lemma,proof,datatype,where,let,in, mathescape, upquote=true, breaklines=true \lstdefinestyle inlinebasicstyle= \lstdefinelanguage Isabelle morekeywords=for,context,inductive,begin,end,locale,fixes,record,type_synonym,definition,fun,function,primrec,where,lemma,theorem,unfolding,by, shows,assumes,and,datatype,using,abbreviation,moreover,have,hence,thus,qed,proof,let,ultimately,show,next,in,if,value, thm,corollary,else,then , sensitive=true , showstringspaces=true , framerule=0pt , xleftmargin=2em , numbers=left , numberstyle= , firstnumber=1 , stepnumber=2 , basicstyle=, backgroundcolor = , keywordstyle = , breaklines=true , showspaces=false , morecomment=[l]-- , morecomment=[s](**) , commentstyle= , morestring=[b]" , literate=↦ \mapsto 1 ∧ \wedge 1 × \times 1 ≡ \equiv 1 ∀ \forall 1 ∃ \exists 1 <times> \times 1 <and> \land 1 <inter> \cap 1 ∈ \in 1 ⇒ \Rightarrow 1 <Rightarrow> \Rightarrow 1 <And> \bigwedge 1 <forall> \forall 1 <in> \in 1 <exists> \exists 1 <subseteq> \subseteq 1 <longrightarrow> \longrightarrow 1 <Longrightarrow> \Longrightarrow 1 <notin> \not\in 1 λ \lambda 1 <lambda> \lambda 1 :: :: 1 <epsilon> \epsilon 1 <alpha> \alpha 1 \⊆ \subseteq 1 <subset> \subset 1 <^sub>m m 1 <longleftrightarrow> \longleftrightarrow 3 <pi> \pi 1 <delta> \delta 1 ⟦ \llbracket 1 ⟧ \rrbracket 1 <lbrakk> \llbracket 1 <rbrakk> \rrbracket 1 ⟹ \Longrightarrow 3 <not> \lnot 1 <le> \leq 1 <rightharpoonup> \rightharpoonup 2 <^sub> <V> V 1 <lparr> \llparenthesis 1 <rparr> \rrparenthesis 1 <leftarrow> \leftarrow 1 <^sub> <O> O 1 <^sub>I {}_{\texttt{I}} 1 <^sub>G {}_{\texttt{G}} 2 <phi> \varphi 1 <Phi> \Phi 1 <psi> \psi 1 <Psi> \Psi 1 <^sub>S {}_{\texttt{S}} 1 <inverse> -1 1 <^sub>O {}_{\texttt{O}} 1 <^bold> \⋀ \bm\bigwedge 1 ⋀ \bigwedge 1 <^bold> <or> \bm\lor 1 <^sub>G {}_{\texttt{G}} 1 <Pi> \Pi 1 <^sub>I {}_{\texttt{I}} 1 \≠ \neq 1 <bottom> \bot 1 <^sub>+ {}_{\texttt{+}} 1 <^bold> <and> \bm\land 1 <^bold> <not> \bm\lnot 1 <^sub>1 1 1 <subpset>1 \supset 1 <^sub>2 2 1 <A> \mathcal{A} 1 <Turnstile> \models 2 <^sub>∀ ∀ 1 <noteq> \neq 1 <^sub>0 0 1 <tau> \tau 1 <^sub> <Omega> Ω 1 <^sub>V V 1 <^bold> <Or> \bm\bigvee 1 <^sub>P {}_{\texttt{P}} 1 <^sub>X {}_{\texttt{X}} 1 ⟹ \Longrightarrow 2 <or> \lor 1 <^sub> <pi> π 1 <^sub>s s 1 <^sub>t t 1 <^sub>a a 1 <^sub>r r 1 <^sub>t t 1 <^sub>e e 1 <^sub>n n 1 <^sub>d d 1 <^sub>i i 1 <^sub>v v 1 <^sub>j j 1 <^sub>b b 1 \∩ \cap 1 <union> \cup 1 <Union> \bigcup 1 <^sup>c <TTurnstile> <^sub>= {}^{c}\models_{=} 1 <open><1 <close>>1 <langle> \langle 1 <rangle> \rangle 1 <ge> \geq 1 <^sup>- <^sup>1 <^sub>C {}^{\texttt{-1}}_{\texttt{C}} 2 <^sup>+ <^sub>C {}^{\texttt{+}}_{\texttt{C}} 1 <circ> <^sub>C \circ^{\texttt{C}} 1 <top> <^sub>C \top_{\texttt{C}} 2 <bottom> <^sub>C \bot_{\texttt{C}} 2 <not> <^sub>C \neg_{\texttt{C}} 2 <squnion> <^sub>C \sqcup_{\texttt{C}} 2 <sqinter> <^sub>C \sqcap_{\texttt{C}} 2 \∃ <^sub>C \exists_{\texttt{C}} 2 ∀ <^sub>C \forall_{\texttt{C}} 2 = <^sub>C =_{\texttt{C}} 2 <sigma> \sigma 2 \∉ \notin 1 ⊕ \oplus 1 <nexists> \nexists 1 <setminus> \setminus 1 1 <bullet> \bullet 1 <^sup>T T 1 _-1 "1 pi^* \pi^{*} 1 <pi> <^sup>* \pi^{*} 1 <V> \mathcal{V} 1 <E> \mathcal{E} 1 <M> \mathcal{M} 1 <F> \mathcal{F} 1 <bar> | 1 of of 1 and and 1 <nu> \nu 1 ccs Theory of computation Discrete optimization ccs Theory of computation Invariants ccs Theory of computation Program verification keywords Bipartite Matching, Graph Algorithms, Isabelle/HOL, Formal Verification † † runningtitle: Formal Primal-Dual Algorithm Analysis † † runningauthor: M. Abdulaziz and T. Ammer † † copyright: Mohammad Abdulaziz and Thomas Ammer † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The Primal-dual paradigm for analysing algorithms is one of the most successful. Its history spans more than 70 years, with the Hungarian Method [ 27 ] being one of the first algorithms for solving weighted bipartite matchings to follow this paradigm. Since then, the paradigm has been used to design algorithms for problems in combinatorial optimisation, including Edmonds’ algorithm for weighted matching in general graphs [ 16 ] , all the way to modern analyses of online matching algorithms [ 13 ] and some of the fastest algorithms for solving flow problems [ 12 ] . In addition to exact algorithms, the primal-dual approach is also cornerstone to the design for a majority of approximation algorithms for optimisation problems, like MaxSAT, set cover, Steiner trees, etc. (cf. Part II of Vazirani’s seminal book on approximation algorithms, which is dedicated to the primal-dual method). In this work we present a series of formal analyses of primal-dual matching algorithms. Our analyses cover a range of primal-dual algorithms: from the HM, arguably the first primal-dual algorithm, to more probabilistic arguments used to analyse online algorithms, including the well-known Adwords algorithm [ 31 ] and the RANKING algorithm [ 25 ] . Our longer term goal is to create a formal library of lemmas and reasoning principles that aid in the analysis of primal-dual algorithms. Availability. We build on an ongoing effort to build a library of combinatorial optimisation in Isabelle/HOL [ 1 ] . We plan to integrate our work in that library. Theory Background. We assume the reader to be familiar with basic graph theory, such as vertices \mathcal{V} , edges \mathcal{E} and paths in graphs, bipartiteness, and adjacency and incidence matrices encoding graphs. Because it eases the formalisation, we identify a graph with its edges and define \mathcal{V}=\bigcup\mathcal{E} . A matching \mathcal{M} in a graph \mathcal{E} is a vertex-disjoint subset of the edges in \mathcal{E} . Matchings covering all vertices are perfect . We search for matchings that are optimum w.r.t. an optimisation objective e.g. the maximisation/minimisation of accumulated real weights. In a primal-dual (PD) method, we maintain an upper bound for the value of the solution, and finally obtain a solution whose value equals the final upper bound (or is close to it), which implies optimality (or sufficient proximity). We encode the optimisation problem into linear (in-)equalities alongside a linear optimisation objective ( linear program/LP ), e.g. \textsf{max}\{c^{T}x.\,Ax\leq b,x\geq 0\} in linear algebra notation. A is usually the incidence matrix, a primal solution is a vector x_{\mathcal{M}}\in\{0,1\}^{|\mathcal{E}|} encoding a matching, and a dual solution \pi is a |\mathcal{V}| -dimensional vector/function \pi:\mathcal{V}\rightarrow\mathbb{R} (“potential”). We write accumulated weights as w(E) for E\subseteq\mathcal{E} , and \pi(\mathcal{V}) for the potentials \pi . For \textsf{max}\{c^{T}x.\,Ax\leq b,x\geq 0\} , the primal , there is a dual \textsf{min}\{b^{T}y.\,A^{T}y\geq c,y\geq 0\} . Vectors x and y satisfying these constraints are feasible primal and dual solutions , for which c^{T}x\leq b^{T}y holds ( weak duality WD ). Furthermore, if ((1-\delta)A\hat{x}-b)^{T}\hat{y}=0 and (1-\delta)(A^{T}\hat{y}-c)^{T}\hat{x}=0 , then (1-\delta)c^{T}\hat{x}=b^{T}\hat{y} and hence both (1-\delta)\hat{x} and \hat{y} are optimum solutions to the respective LPs ( complementary slackness CS ). If \delta=0 , \hat{x} is an exact optimum, otherwise \hat{x} satisfies an approximation guarantee. For further details, e.g. other LP types and their versions of WD and CS, we refer to the literature [ 35 ,

Read the complete text