A Formal Analysis of RANKING

02/27/2023
by   Mohammad Abdulaziz, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset