Source-linked AI summary
When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
Nikhil Bansal, Anupam Gupta, Jian Li, Julian Mestre, Viswanath Nagarajan, Atri Rudra
TL;DR
The paper studies adaptive probing policies for stochastic matching when probing reveals edges and successful probes force matching decisions under vertex query limits. It uses LP-based randomized rounding and related reductions to obtain constant-factor guarantees across weighted, unweighted, and online variants.
Problem
Stochastic matching asks how to adaptively probe uncertain edges to maximize the expected cardinality or weight of a matching under vertex timeouts; greedy methods can be arbitrarily bad with weights.
Method
The paper models matching as stochastic set packing and rounds an LP solution using a random permutation, probing safe items probabilistically according to their LP values.
Results
The paper gives a 4-approximation for weighted stochastic matching on general graphs and a 3-approximation on bipartite graphs, while also deriving improved guarantees for related unweighted and set-packing variants.
Takeaways & Limitations
The LP-rounding framework provides constant-factor algorithms for stochastic matching and extends to broader stochastic packing and online matching settings.
Takeaways & Limitations
The greedy-based improvement applies only to the unweighted problem because greedy has an unbounded approximation ratio with weights, and the online setting requires reasoning without knowing the realized buyer graph in advance.
Abstract
from arXiv · showhide
Consider a random graph model where each possible edge $e$ is present independently with some probability $p_e$. Given these probabilities, we want to build a large/heavy matching in the randomly generated graph. However, the only way we can find out whether an edge is present or not is to query it, and if the edge is indeed present in the graph, we are forced to add it to our matching. Further, each vertex $i$ is allowed to be queried at most $t_i$ times. How should we adaptively query the edges to maximize the expected weight of the matching? We consider several matching problems in this general framework (some of which arise in kidney exchanges and online dating, and others arise in modeling online advertisements); we give LP-rounding based constant-factor approximation algorithms for these problems. Our main results are the following: We give a 4 approximation for weighted stochastic matching on general graphs, and a 3 approximation on bipartite graphs. This answers an open question from [Chen etal ICALP 09]. Combining our LP-rounding algorithm with the natural greedy algorithm, we give an improved 3.46 approximation for unweighted stochastic matching on general graphs. We introduce a generalization of the stochastic online matching problem [Feldman etal FOCS 09] that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.
1 Introduction
The paper develops LP-rounding algorithms for stochastic matching under edge uncertainty, probing limits, and online buyer behavior. It obtains improved constant-factor guarantees across weighted, unweighted, multipleround, online, and stochastic packing variants.
- Stochastic matching: The problem asks how to maximize expected matching weight when edge existence is uncertain, probing successful edges commits them to the matching, and each vertex has a probing limit.The model is motivated by kidney exchanges and online dating.
- Weighted stochastic matching: 4-approximation algorithms solve weighted stochastic matching on general graphs, improving to 3-approximation for bipartite graphs.These results address an open question from prior work.
- Unweighted stochastic matching: 3.46-approximation is achieved for unweighted stochastic matching in general graphs by combining LP-rounding with the greedy algorithm.The LP-rounding algorithm alone matches the prior greedy algorithm's 4-approximation, while their combination improves the bound.
- Online stochastic matching: A 7.92-approximation algorithm extends stochastic matching to online buyers with uncertain preferences, limited attention spans, timeouts, and first-liked-item purchasing.The model generalizes earlier online stochastic matching settings with binary preferences and unit timeouts.
- Extensions: The framework also gives constant-factor approximation algorithms for weighted multipleround stochastic matching and a 2k-approximation for weighted stochastic k-set packing.The k-set-packing generalization implies an 8-approximation for stochastic matching, while exploiting matching structure yields stronger ratios in the main matching results.
- General implications: The algorithms yield non-adaptive strategies that are only a constant factor worse than the adaptive optimum for the corresponding problems.The LP-based analysis also applies to broader stochastic packing settings.
2 Stochastic Matching
The paper formulates stochastic matching with vertex patience limits and develops LP-based rounding algorithms for weighted matching. It obtains constant-factor guarantees across general and bipartite graphs, including matching-probing strategies and an improved unweighted bound.
- Problem: Each edge has a probability and weight, while each vertex may be probed only up to its patience parameter.A successful probe matches the edge’s endpoints; probing consumes patience when unsuccessful or successful.
- LP relaxation: The LP uses y_e for the probability of probing edge e and x_e = p_e · y_e for the probability that e produces a match.The LP is a relaxation because every adaptive strategy satisfies its probing and matching constraints.
- General graphs: 5.75-approximation is achieved by randomly ordering edges and probing safe edges with probability y_e/α.This simpler algorithm illustrates the LP approach and also supports the later online stochastic matching extension.
- Bipartite and general graphs: The dependent-rounding algorithm yields a matching-probing strategy, where edges are probed in rounds and each round is a matching.The strategy is only a constant factor worse than the optimal edge-probing strategy.
- Bipartite and general graphs: 3-approximation is obtained for bipartite graphs and 4-approximation for general graphs.The bipartite guarantee is based on ROUND-COLOR-PROBE; the general-graph algorithm randomly partitions vertices and applies the bipartite procedure.
- Unweighted matching: 3.46-approximation for unweighted general graphs comes from combining the LP-rounding algorithm with the greedy algorithm.The combination exploits their different worst cases across edge-probability regimes, but this argument does not extend to weighted matching because greedy has an unbounded approximation ratio there.
3 Stochastic Online Matching (Revisited)
The paper extends stochastic online matching to buyers with uncertain preferences, weights, and patience limits. It solves an LP before arrivals, applies randomized online offers, and proves a constant-factor approximation relative to the adaptive optimum.
- Model: Buyers arrive independently by type, like offered items with type-dependent probabilities, purchase the first liked item, and may receive at most t_b offers.Items are single-copy goods, and revenue depends on the purchased item and buyer type.
- Scope: The extension generalizes stochastic online matching to weighted buyers with preference uncertainty and timeouts, while its guarantee is in expectation.The earlier model is recovered when preferences and weights are binary and patience equals one.
- Algorithm: The algorithm solves an LP on the expected graph before arrivals, then offers unsold items in random order with probabilities scaled by α.Only the first buyer of each type is offered items; later buyers of that type are not served by this policy.
- Analysis: The optimal adaptive value is at most E[LP(Ĝ)], where Ĝ is the realized instance graph.This follows by allowing a strategy to see the realized buyers before selling and bounding its value by the corresponding LP.
- Analysis: The algorithm obtains a constant fraction of the LP value through bounds on item availability, buyer timeouts, and prior matches.The proof analyzes the expected revenue from the first arriving buyer of each type.
- Analysis: LP(G) ≥ E[LP(Ĝ)] connects the expected-graph LP used by the algorithm to the expected LP of the realized instance.The proof constructs feasible dual solutions for each realized graph from an optimal dual solution on the expected graph.
4 Stochastic k-Set Packing
The paper generalizes stochastic matching to stochastic k-set packing, where items have random profits and sizes with column sparsity at most k. An LP-based random-permutation algorithm yields a 2k-approximation for safe adaptive strategies.
- Problem: Stochastic k-set packing packs items with random profits and d-dimensional sizes into a capacity vector, revealing each item's realization only when probed.The objective is to choose an adaptive strategy maximizing expected obtained profit.
- Problem: The parameter k is the column sparsity: each item has positive size in at most k coordinates.This parameter controls the approximation guarantee developed in the section.
- Reduction: Stochastic matching is modeled as stochastic 4-set packing using vertex-availability and per-vertex probing-capacity coordinates.Each edge becomes an item, and every realized size vector has at most four ones.
- Algorithm: The algorithm solves an LP, randomly permutes columns, and probes a column only when all coordinates in its support have positive residual capacity.The LP solution supplies probing probabilities, while unsafe columns are skipped.
- Guarantee: 2k-approximation is obtained by bounding each supported constraint's tightness probability and applying a union bound before linearity of expectations.The analysis uses the indicators for constraints that are tight when a column is considered.
5 Final Remarks
The final remarks place the paper in context and identify subsequent progress on unweighted stochastic matching. They also note that the computational complexity of stochastic matching remains unresolved.
- Context: The paper's bounds improve on those in its earlier ESA extended abstract.The authors state that the bounds in Section 2 are slightly better than the extended-abstract claims.
- Subsequent work: Adamczyk later proved that greedy is a 2-approximation for unweighted stochastic matching, improving the paper's Theorem 3 bounds.The passage attributes this later result to Adamczyk.
- Open question: Whether stochastic matching is NP-complete remains an open question.
A Cardinality Constrained Multiple Round Stochastic Matching
This section studies stochastic matching when probing occurs over multiple rounds, with each round restricted to a bounded-size matching. An LP relaxation and randomized rounding produce a constant-factor approximation for this cardinality-constrained setting.
- Problem: Multiple-round stochastic matching probes edges in at most k rounds, with each round a matching of size at most C.Vertices may still be probed at most t_i times and only while unmatched.
- LP relaxation: The LP uses the convex hull of matchings of size at most C and relaxes adaptive strategies in polynomial time.An optimal adaptive strategy induces a feasible LP solution with the same objective value.
- Algorithm: The algorithm solves the LP, decomposes each round's solution into a convex combination of bounded-size matchings, and probes selected edges that are safe.The construction uses the integrality of the matching polytope.
- Analysis: Safety requires that an edge is unprobed, both endpoints are unmatched, and neither endpoint has timed out.The analysis bounds the failure probability using these five possible obstructions.
- Guarantee: 20-approximation is achieved for multiple-round stochastic matching by setting α = 10.The guarantee follows from a lower bound on the probability that an edge remains safe in a round.
B Unweighted Stochastic Matching: A Greedy Algorithm
For unweighted stochastic matching, the paper analyzes a greedy policy that processes edges by non-increasing existence probability and probes each safe edge. The section presents a simpler analysis with a 5-approximation guarantee.
- Objective: The unweighted objective is to maximize the expected number of matched edges when every edge has unit weight.
- Algorithm: The greedy algorithm orders edges by non-increasing p_e and probes an edge exactly when it is safe.An edge is safe when neither endpoint has been matched or timed out.
- Analysis: The paper gives a significantly simpler analysis of the greedy algorithm than the earlier analysis by Chen et al.
B.1 The Analysis
The analysis charges the greedy algorithm’s value to an optimal LP solution through events caused by matching or vertex timeouts. Combining these bounds shows that greedy achieves a 5-approximation.
- Event definitions: The analysis defines events for when an edge is blocked by an existing match or by a vertex timeout, with probing occurring only when neither event holds.These events support the charging arguments against the LP solution.
- Charging arguments: The first charging argument bounds the value written during greedy executions by ALG, the algorithm’s expected value.An edge is matched or probed at most once, allowing total expected written value to be identified with ALG.
- Charging arguments: A second charging argument uses α-values to show that timeout events read value proportional to t_a p_g/2 from adjacent edges.When a vertex a times out, t_a incident edges have already been probed, which raises the α-value of an adjacent edge g.
- Charging arguments: The total value read from edges is at most the final value A maintained by the greedy algorithm.This connects the timeout-event charge to the algorithm’s accumulated value.
- Final guarantee: 5 ALG ≥ the optimal LP objective, so the greedy algorithm is a 5-approximation.The bound follows by adding the two charging lemmas and combining them with the LP-related inequality.