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

Gagan Aggarwal, Gagan Goel, Chinmay Karande, Aranyak Mehta

Abstract

This paper introduces Perturbed-Greedy, the first optimal randomized algorithm for the online vertex-weighted bipartite matching problem. By applying specific random multiplicative "perturbations" to vertex weights, the algorithm achieves a competitive ratio of $1 - 1/e$ (~0.632). This result matches the theoretical upper bound and effectively solves a long-standing challenge in online allocation and ad auctions, providing a unified framework that generalizes previous results for unweighted matching.

Introduction

Online bipartite matching is a fundamental problem in computer science with significant applications in internet advertising and resource allocation. In this model, we consider a bipartite graph $G = (U \cup V, E)$. The set of "offline" vertices $U$ is known in advance, while "online" vertices $V$ arrive sequentially. Upon the arrival of a vertex $v \in V$, an algorithm must immediately and irrevocably decide whether to match $v$ to an available neighbor $u \in U$.

The objective is to maximize the total weight of the matched vertices in $U$. In the unweighted case, where all weights $b_u = 1$, the classic RANKING algorithm [KVV90] is known to be $(1 - 1/e)$-competitive. However, when vertices have arbitrary weights $b_u$, simple extensions fail. A standard Greedy approach, which always picks the highest-weight neighbor, achieves only a 0.5 competitive ratio. Conversely, the RANKING algorithm, which ignores weights, can perform as poorly as $1/n$ on weighted instances. This paper addresses the gap by proposing an algorithm that maintains the optimal $1 - 1/e$ ratio for arbitrary vertex weights.

The Perturbed-Greedy Algorithm

The authors propose Perturbed-Greedy, a randomized algorithm that balances the weight-sensitive nature of Greedy with the randomization benefits of RANKING. The algorithm operates by independently perturbing the weight of each offline vertex before the online matching process begins.

Algorithm 1: The Perturbed-Greedy procedure for online vertex-weighted bipartite matching.

The logic follows three primary steps:

  1. Pre-processing: For every offline vertex $u \in U$, a number $x_u$ is picked uniformly at random from the interval $[0, 1]$.
  2. Perturbation Function: A scaling function is defined as $\psi(x) := 1 - e^{-(1-x)}$.
  3. Online Matching: As each online vertex $v \in V$ arrives, it is matched to the unmatched neighbor $u$ that maximizes the "perturbed" weight $b_u \cdot \psi(x_u)$. Ties are broken consistently, for example, by vertex ID.

This approach effectively bridges the gap between Greedy and RANKING. If weights are highly skewed, the $b_u$ term dominates, causing the algorithm to behave like Greedy. If weights are equal, the $\psi(x_u)$ term determines the matching order, causing it to behave like RANKING.

Key Insights and Theoretical Analysis

The success of Perturbed-Greedy rests on several critical theoretical insights:

  • The Power of Independent Randomness: The algorithm demonstrates that independent perturbations are sufficient. There is no need for global coordination or knowledge of the weight distribution to achieve optimality.
  • The Structure of $\psi(x)$: The specific function $\psi(x) = 1 - e^{-(1-x)}$ is not arbitrary. It emerges naturally from the "charging" analysis used to prove the competitive ratio, representing the unique solution to a differential equation that ensures the $(1 - 1/e)$ bound holds across all possible input graphs.
  • Unified Theory of Allocations: The paper establishes a connection between vertex-weighted matching and "single-bid" budgeted allocations. This provides a "smooth interface" between the "small bids" case (where individual bids are negligible compared to total budgets) and the "large bids" case addressed here.

Results and Impact

The primary result of this work is the proof that Perturbed-Greedy is $(1 - 1/e)$-competitive. This is the best possible ratio for any randomized algorithm in this adversarial model. Furthermore, the algorithm is a true generalization: when all weights $b_u$ are equal, Perturbed-Greedy reduces exactly to the classic RANKING algorithm.

Beyond theoretical matching, the authors show that their algorithm effectively solves the "single-bid" budgeted allocation problem. This is a core component in modeling sponsored search auctions, where advertisers have a fixed budget and a single bid value for all relevant queries.

Discussion and Future Work

While Perturbed-Greedy solves the vertex-weighted problem, challenges remain for more complex models. If weights depend on the specific edge $(u, v)$ rather than just the vertex $u$, the competitive ratio drops to $O(1/n)$ in an adversarial arrival model.

Additionally, while this paper addresses "single-bid" and "small-bid" budgeted allocations, the "unrestricted" case—where bids can be large and vary per item—remains an open problem. The authors suggest that the perturbation-based approach introduced here might provide the necessary framework for a unified solution to the general budgeted allocation problem.

Summary updated

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 \emph{online bipartite matching} problem for which Karp, Vazirani and Vazirani gave an optimal $\left(1-\frac{1}{e}\right)$-competitive algorithm in their seminal work~\cite{KVV90}. Our main result is an optimal $\left(1-\frac{1}{e}\right)$-competitive randomized algorithm for general vertex weights. We use \emph{random perturbations} of weights by appropriately chosen multiplicative factors. Our solution constitutes the first known generalization of the algorithm in~\cite{KVV90} in this model and provides new insights into the role of randomization in online allocation problems. It also effectively solves the problem of \emph{online budgeted allocations} \cite{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 \cite{MSVV05, BJN07} which apply when the bids are much smaller than the budgets.
BibTeX
@inproceedings{aggarwal2011online,
  author = {Gagan Aggarwal and Gagan Goel and Chinmay Karande and Aranyak Mehta},
  title = {{Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations}},
  booktitle = {SODA},
  year = {2011},
  url = {https://openreview.net/forum?id=4JsH8QSsweo},
}
Figure