Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations
Venue
Proceedings of ACM-SIAM Symposium on Discrete Algorithms (2011)
Publication Year
2011
Authors
Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta
BibTeX
Abstract
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.
