Competitive Algorithms for Online Weighted Bipartite Matching and its Variants
share
Online bipartite matching has been extensively studied. In the unweighted setting, Karp et al. gave an optimal (1 - 1/e)-competitive randomized algorithm. In the weighted setting, optimal algorithms have been achieved only under assumptions on the edge weights. For the general case, little was known beyond the trivial 1/2-competitive greedy algorithm. Recently, Fahrbach et al. have presented an 0.5086-competitive algorithm (for the problem in a model, namely free-disposal), overcoming the long-standing barrier of 1/2. Besides, in designing competitive algorithms for the online matching problem and its variants, several techniques have been developed, in particular the primal-dual method. Specifically, Devanur et al. gave a primal-dual framework, unifying previous approaches and Devanur and Jain provided another scheme for a generalization of the online matching problem. In this paper, we present competitive algorithms for the online weighted bipartite matching in different models; in particular we achieve the optimal (1-1/e) competitive ratio in the free-disposal model and in other model, namely stochastic reward. Our work also unifies the previous approaches by the mean of the primal-dual technique with configuration linear programs.
READ FULL TEXT