Beating Greedy for Stochastic Bipartite Matching

Buddhima Gamlath, Sagar Kale, Ola Svensson

Abstract

We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge $e$ independently exists with probability $p_e$. We can query whether an edge exists or not, but if it does exist, then we have to take it into our solution. In the unweighted case, one can query edges in the order given by the classical online algorithm of Karp, Vazirani, and Vazirani to get a $(1-1/e)$-approximation. In contrast, the previously best known algorithm in the weighted case is the $(1/2)$-approximation achieved by the greedy algorithm that sorts the edges according to their weights and queries in that order. Improving upon the basic greedy, we give a $(1-1/e)$-approximation algorithm in the weighted query-commit model. We use a linear program (LP) to upper bound the optimum achieved by any strategy. The proposed LP admits several structural properties that play a crucial role in the design and analysis of our algorithm. We also extend these techniques to get a $(1-1/e)$-approximation algorithm for maximum bipartite matching in the price-of-information model introduced by Singla, who also used the basic greedy algorithm to give a $(1/2)$-approximation.

Introduction

Maximum bipartite matching is a cornerstone of combinatorial optimization, but real-world applications—like kidney exchanges or online dating—often involve uncertainty. This paper addresses two primary stochastic models:

  1. Query-Commit Model: You know the probability $p_e$ that an edge $e$ exists. You can "query" the edge to see if it’s there. If it exists, you must include it in your matching (the "commit" part). This creates a dilemma: querying a mediocre edge might prevent you from taking a much better edge later if they share a vertex.
  2. Price-of-Information (PoI) Model: Edge weights are random variables. To find out the actual weight of an edge, you must pay a specific cost $\pi_e$. The goal is to maximize the total weight of the matching minus the total probing costs.
Figure 1: A bipartite graph illustrating the query-commit model, where edges exist with specific probabilities (e.g., 4/9, 2/9), forcing strategic decisions.

In the unweighted case, a $(1 - 1/e)$ approximation has been known since 1990. However, for the weighted case, the best known approach was a simple greedy algorithm (querying edges in descending order of weight), which only guarantees a $1/2$ approximation. This paper finally "beats greedy" by achieving a $(1 - 1/e)$ ratio.

Methodology

The authors propose a two-stage framework to solve these problems efficiently:

Stage 1: LP Upper Bounding

They develop a Linear Program (LP) to upper-bound the expected value of any optimal strategy. The constraints are based on the probability that at least one edge in a subset $F$ exists. Because this probability function is submodular, the LP can be solved in polynomial time using the ellipsoid method with a submodular minimization separation oracle.

Stage 2: Algorithm Design via Prophet Secretary

The authors observe that the extreme points of their LP polytope have a "chain" structure (nested sets). They use this structure to define a specific query order for each vertex. To resolve "collisions" (when multiple vertices on one side try to match with the same neighbor), they adapt techniques from the Prophet Secretary problem. They assign each vertex a random arrival time and use dynamic, time-dependent thresholds to decide whether to commit to a queried edge.

Figure 2: An example of edge probability assignments used to illustrate the reduction of complex stochastic models to multi-point distributions.

For the Price-of-Information model, they use a reduction that transforms the problem into a "multiple-weight" version of the query-commit model, allowing them to apply their core algorithmic insights to both settings.

Key Insights and Ideas

  • The "Chain" Property: A crucial "aha moment" is the realization that the tight constraints of the LP's extreme points form a chain. This nested structure provides a natural, optimal order in which to query edges incident to a single vertex.
  • Contention Resolution as an Auction: The authors cleverly reframe the bipartite matching problem as a collection of independent "prophet secretary" instances. Each vertex on one side acts as a "buyer" arriving at a random time, and the algorithm uses dynamic pricing (thresholds) to ensure that the overall matching remains high-weight despite local conflicts.
  • Lattice Families for Multi-point Distributions: To handle edges with many possible weights, the authors generalize their LP to work over lattice families, maintaining polynomial-time solvability while capturing complex correlations.

Key Results

  • Weighted Query-Commit: The authors provide the first algorithm to achieve a $(1 - 1/e) \approx 0.632$ approximation, improving upon the previous $0.5$ greedy limit.
  • Price-of-Information: They achieve a $(1 - 1/e)$ approximation for this model as well, also improving upon the previous $1/2$ ratio established by Singla (2018).
  • Polynomial Efficiency: All proposed algorithms, including the LP solver and the contention resolution strategy, run in polynomial time.

Limitations and Future Work

While the $(1 - 1/e)$ result is a significant breakthrough for bipartite graphs, extending these "beating greedy" techniques to general graphs remains an open challenge, as current approximation ratios there are lower (around $1/4$). Additionally, while $(1 - 1/e)$ is a classic barrier in online algorithms, future work could explore if even better ratios are possible with more complex, non-linear-program-based strategies.

Summary updated

Abstract

We consider the maximum bipartite matching problem in stochastic settings, namely the query-commit and price-of-information models. In the query-commit model, an edge e independently exists with probability pe. We can query whether an edge exists or not, but if it does exist, then we have to take it into our solution. In the unweighted case, one can query edges in the order given by the classical online algorithm of Karp, Vazirani, and Vazirani [20] to get a (1 – 1/e)-approximation. In contrast, the previously best known algorithm in the weighted case is the (1/2)-approximation achieved by the greedy algorithm that sorts the edges according to their weights and queries in that order. Improving upon the basic greedy, we give a (1 – 1/e)-approximation algorithm in the weighted query-commit model. We use a linear program (LP) to upper bound the optimum achieved by any strategy. The proposed LP admits several structural properties that play a crucial role in the design and analysis of our algorithm. We also extend these techniques to get a (1 – 1/e)-approximation algorithm for maximum bipartite matching in the price-of-information model introduced by Singla [25], who also used the basic greedy algorithm to give a (1/2)-approximation.
BibTeX
@inproceedings{gamlath2019beating,
  author = {Buddhima Gamlath and Sagar Kale and Ola Svensson},
  title = {{Beating Greedy for Stochastic Bipartite Matching}},
  booktitle = {SODA},
  year = {2019},
  doi = {10.1137/1.9781611975482.176},
}
Figure