Online vertex-weighted bipartite matching and single-bid budgeted allocations

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