C&O Reading Group - Vihan Shah

Title: An Optimal Algorithm for Online Bipartite Matching 

Abstract: We consider the bipartite matching problem in the online setting where vertices on the left arrive in an arbitrary order along with all their edges. Once a vertex arrives, the algorithm has to match the vertex (or can choose to not match it) and this decision cannot be changed later. Karp, Vazirani, and Vazirani give an algorithm for this problem with a competitive ratio of 1-1/e and also show it is optimal.