2026-08-11T04:36:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18378 2024-03-06T11:01:44Z ddc:004 open_access

A Formal Analysis of RANKING Abdulaziz, Mohammad Madlener, Christoph Matching Theory Formalized Mathematics Online Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mohammad Abdulaziz and Christoph Madlener 2023 Is Part Of LIPIcs, Volume 268, 14th International Conference on Interactive Theorem Proving (ITP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITP.2023.3 urn:nbn:de:0030-drops-183785 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2023.3 eng https://creativecommons.org/licenses/by/4.0/legalcode