2021/11/02 by Nguyễn Kim Thắng, Thang, Nguyen Kim
Computer Science · #Optimization and Search Problems #Complexity and Algorithms in Graphs #Cryptography and Data Security
paper · pdf · doi:10.48550/arxiv.2111.01718
Online bipartite matching has been extensively studied. In the unweighted\nsetting, Karp et al. gave an optimal (1 - 1/e)-competitive randomized\nalgorithm. In the weighted setting, optimal algorithms have been achieved only\nunder assumptions on the edge weights. For the general case, little was known\nbeyond the trivial 1/2-competitive greedy algorithm. Recently, Fahrbach et\nal. have presented an 0.5086-competitive algorithm (for the problem in a model,\nnamely free-disposal), overcoming the long-standing barrier of 1/2. Besides, in\ndesigning competitive algorithms for the online matching problem and its\nvariants, several techniques have been developed, in particular the primal-dual\nmethod. Specifically, Devanur et al. gave a primal-dual framework, unifying\nprevious approaches and Devanur and Jain provided another scheme for a\ngeneralization of the online matching problem.\n In this paper, we present competitive algorithms for the online weighted\nbipartite matching in different models; in particular we achieve the optimal\n(1-1/e) competitive ratio in the free-disposal model and in other model,\nnamely stochastic reward. Our work also unifies the previous approaches by the\nmean of the primal-dual technique with configuration linear programs.\n