This talk will give a brief introduction to the online primal-dual method through the lens of online bipartite matching. We will begin with the classic online bipartite matching problem and discuss two well-known algorithms: RANKING and WATER-LEVEL. Using these as examples, we will explore how a primal-dual perspective can be used to analyze their performance. The focus will be on how the analysis can be carried out in an online fashion, highlighting a general approach that applies to a broad class of algorithms for online bipartite matching.
