Beating Greedy for Stochastic Bipartite Matching

Buddhima Gamlath, Sagar Kale, Ola Svensson

TL;DR

This paper presents new algorithms for the stochastic bipartite matching problem, achieving a significant improvement over previous methods. By leveraging linear programming and novel structural insights, the authors provide a $(1 - 1/e)$-approximation for both the "query-commit" and "price-of-information" models, outperforming the prior best of $1/2$.

What Problem Does This Paper Address?

The paper tackles the problem of finding a maximum weight bipartite matching when the input graph's edges are not fully known upfront. Specifically, it focuses on two "stochastic" settings:

  1. Query-Commit Model: Edges exist with a certain probability. If an edge is queried and found to exist, the algorithm must include it in the matching. This models situations where you can probe for information, but once you know something exists, you're committed to using it. The unweighted version of this problem has a known $(1 - 1/e)$ approximation, but the weighted version was stuck at $1/2$ using a simple greedy approach.
  2. Price-of-Information (PoI) Model: Edges have random weights. To learn an edge's actual weight, you must pay a cost. The goal is to select a matching that maximizes the total weight of matched edges minus the total cost of querying their weights. Again, the best known algorithm for this was a $1/2$-approximation.

The core challenge is to design algorithms that can make informed decisions about which edges to query and commit to, balancing the potential reward of a high-weight edge against the risk of commitment and the cost of information.

Methods

The authors introduce a two-stage approach:

  1. Linear Programming (LP) Formulation: They formulate a linear program to establish an upper bound on the optimal achievable matching weight in both models. This LP captures the constraints imposed by the problem's structure (e.g., a vertex can only be matched once).
  2. Structural Analysis of LP Polytope: A key innovation is analyzing the "extreme points" of the polytope defined by the LP constraints. They discover that these extreme points have a specific "chain-like" structure. This structure allows them to derive probability distributions over edge query orders.
  3. Algorithm Design:
    • Query-Commit: They use the derived probability distributions to guide the query order. For each vertex in one partition (say, 'A'), they define a distribution over permutations of its incident edges. By querying edges in this order and using a strategy inspired by the "prophet secretary problem" (a classic online decision problem), they achieve the $(1 - 1/e)$ approximation.
  4. Price-of-Information: They adapt the query-commit approach. First, they transform the problem by defining "effective" edge values that account for querying costs. Then, they apply a similar LP-based strategy, but with a more complex polytope structure reflecting the edge-value pairs. The algorithm carefully decides when to query an edge to learn its true weight, balancing the cost against the potential gain.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • LP as a Powerful Tool: The paper demonstrates how a carefully constructed LP can not only bound the optimal solution but also reveal crucial structural properties of the problem.
  • The Power of Structure: The "chain-like" structure of the LP polytope's extreme points is the lynchpin. It provides a way to deterministically guide the randomized querying process for a $(1 - 1/e)$ guarantee.
  • Connecting to Prophet Secretary: The authors cleverly relate the problem to the prophet secretary problem, leveraging existing results and adapting them to the bipartite matching context. This allows them to handle the "commitment" aspect of the query-commit model and the "cost of information" in the PoI model.
  • Beyond Simple Greedy: The work shows that a simple greedy strategy (sorting by weight) is suboptimal for weighted stochastic matching, and a more sophisticated LP-based approach is necessary for better performance.

Key Results

  • Weighted Query-Commit: A $(1 - 1/e)$-approximation algorithm is presented, improving from the previous best of $1/2$.
  • Price-of-Information: A $(1 - 1/e)$-approximation algorithm is presented, also improving from the previous best of $1/2$.
  • The algorithms are polynomial-time.

Limitations and Future Work

  • Assumptions: The analysis often assumes probabilities $p_e$ are strictly between 0 and 1. The paper mentions that these can be handled by scaling, but it's a technical detail. For the PoI model, it assumes discrete distributions for edge values, which is addressed by a "geometric grouping" technique.
  • General Graphs: The current work focuses on bipartite graphs. Extending these techniques to general graphs would be a natural next step.
  • Adaptive vs. Non-Adaptive: While the algorithms are adaptive in their querying, exploring non-adaptive strategies could be another research direction.
  • Other Stochastic Models: The paper hints at connections to other stochastic optimization problems, suggesting potential for broader applications of their techniques.

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},
}

Loading related content...

Figure