DROPS

Document

Short Paper

DOI: 10.4230/LIPIcs.ITP.2026.33

Formal Primal-Dual Algorithm Analysis (Short Paper)

Authors: Mohammad Abdulaziz, Thomas Ammer, and Christoph Madlener

Published in: LIPIcs, Volume 382, 17th International Conference on Interactive Theorem Proving (ITP 2026)

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.

Cite as

Mohammad Abdulaziz, Thomas Ammer, and Christoph Madlener. Formal Primal-Dual Algorithm Analysis (Short Paper). In 17th International Conference on Interactive Theorem Proving (ITP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 382, pp. 33:1-33:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abdulaziz_et_al:LIPIcs.ITP.2026.33,
  author =	{Abdulaziz, Mohammad and Ammer, Thomas and Madlener, Christoph},
  title =	{{Formal Primal-Dual Algorithm Analysis}},
  booktitle =	{17th International Conference on Interactive Theorem Proving (ITP 2026)},
  pages =	{33:1--33:9},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-436-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{382},
  editor =	{Komendantskaya, Ekaterina and Nipkow, Tobias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2026.33},
  URN =		{urn:nbn:de:0030-drops-270075},
  doi =		{10.4230/LIPIcs.ITP.2026.33},
  annote =	{Keywords: Bipartite Matching, Graph Algorithms, Isabelle/HOL, Formal Verification}
}

Document

DOI: 10.4230/LIPIcs.ITP.2023.3

A Formal Analysis of RANKING

Authors: Mohammad Abdulaziz and Christoph Madlener

Published in: LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023)

Abstract

We describe a formal correctness proof of RANKING, an online algorithm for online bipartite matching. An outcome of our formalisation is that it shows that there is a gap in all combinatorial proofs of the algorithm. Filling that gap constituted the majority of the effort which went into this work. This is despite the algorithm being one of the most studied algorithms and a central result in theoretical computer science. This gap is an example of difficulties in formalising graphical arguments which are ubiquitous in the theory of computing.

Cite as

Mohammad Abdulaziz and Christoph Madlener. A Formal Analysis of RANKING. In 14th International Conference on Interactive Theorem Proving (ITP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 268, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdulaziz_et_al:LIPIcs.ITP.2023.3,
  author =	{Abdulaziz, Mohammad and Madlener, Christoph},
  title =	{{A Formal Analysis of RANKING}},
  booktitle =	{14th International Conference on Interactive Theorem Proving (ITP 2023)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-284-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{268},
  editor =	{Naumowicz, Adam and Thiemann, Ren\'{e}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.3},
  URN =		{urn:nbn:de:0030-drops-183785},
  doi =		{10.4230/LIPIcs.ITP.2023.3},
  annote =	{Keywords: Matching Theory, Formalized Mathematics, Online Algorithms}
}

Search Results

Documents authored by Madlener, Christoph

Formal Primal-Dual Algorithm Analysis (Short Paper)

Abstract

Cite as

A Formal Analysis of RANKING

Abstract

Cite as

Thanks for your feedback!

Could not send message