Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations

Original · EN

We study the following vertex-weighted online bipartite matching problem: G(U, V, E) is a bipartite graph. The vertices in U have weights and are known ahead of time, while the vertices in V arrive online in an arbitrary order and have to be matched upon arrival. The goal is to maximize the sum of weights of the matched vertices in U. When all the weights are equal, this reduces to the classic online bipartite matching problem for which Karp, Vazirani and Vazirani gave an optimal (1-1/e)-competitive algorithm in their seminal work KVV90. Our main result is an optimal (1-1/e)-competitive randomized algorithm for general vertex weights. We use random perturbations of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in KVV90 in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of online budgeted allocations MSVV05 in the case when an agent makes the same bid for any desired item, even if the bid is comparable to his budget - complementing the results of MSVV05, BJN07 which apply when the bids are much smaller than the budgets.