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

Gagan Aggarwal, Gagan Goel, Chinmay Karande +1

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…