Online matching algorithms with randomized primal dual analysis

Abstract

The thesis studies several online matching problems, which were initiated by Karp, Vazirani, and Vazirani in 1990. In their work, the online bipartite matching problem is proposed, with an optimal algorithm called Ranking that is $(1-1/e)$- competitive. In particular, the thesis focuses on two generalizations of the initial model: 1) online vertex-weighted bipartite matching with random arrivals and 2) fully online matching. The first one considers the simple stochastic assumption (random arrivals) to the vertex-weighted generalization and proves the generalized Ranking algorithm is $0.6534$-competitive in the setting. The second considers a new fully online model, where all vertices in the given graph arrive online. Meanwhile, the graph can be bipartite or general, the Ranking algorithm is proved to be ($0.5671$ and $0.5211$)-competitive in the bipartite case and general case.

Another problem studied is the oblivious matching problem, which is another viewpoint that models the real-world matching related applications that require algorithms to make decisions with incomplete information. On the other hand, matching with a randomized greedy approach is a very classic algorithm family initiated by Dyer and Frieze in 1991, which can be naturally used in oblivious matching. The thesis revisits the first beating-$0.5$ algorithm in this family, the Modified Randomized Greedy algorithm (MRG) given by Aronson et al. in 1995. In particular, the thesis studies a weaker version of the MRG algorithm, called Randomized Decision Order(RDO). The approximation ratio of RDO is proved to be $0.639$ and $0.531$ on bipartite graphs and general graphs. It not only improves the analysis of MRG (from $0.5+1/400000$ to $0.531$) but also improves the current best ratio for oblivious matching on general graphs (from $0.526$ to $0.531$). Besides, an edge-weighted generalization of RDO is proposed and proved to be $0.501$-approximate, which is the first non-trivial result for the edge-weighted oblivious matching problem.

Furthermore, the thesis develops the applications and understandings of the Online Randomized Primal-Dual Framework proposed by Devanur et al. in 2013. All the analyses in the thesis are driven by the framework with several novel charging methods designed for different models and algorithms respectively.