Beating greedy for stochastic bipartite matching

DOI10.1137/1.9781611975482.176zbMATH Open1432.68569arXiv1909.12760OpenAlexW2903354203MaRDI QIDQ5236367FDOQ5236367

Ola Svensson, Sagar Kale, Buddhima Gamlath

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1909.12760

Recommendations

• When LP is the cure for your matching woes: improved bounds for stochastic matchings (extended abstract)
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• Stochastic matching with commitment
• Stochastic Matching with Few Queries: New Algorithms and Tools
• Improved approximation algorithms for stochastic matching

Mathematics Subject Classification ID

Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Economics of information (91B44) Matching models (91B68)

Cited In (8)

• Prophet Matching with General Arrivals
• Fcfs infinite bipartite matching of servers and customers
• Lazy Gale-Shapley for many-to-one matching with partial information
• Prophet secretary for combinatorial auctions and matroids
• Truthful Matching with Online Items and Offline Agents
• Pandora Box problem with nonobligatory inspection: hardness and approximation scheme
• Edge-weighted online bipartite matching
• Tradeoffs between information and ordinal approximation for bipartite matching

This page was built for publication: Beating greedy for stochastic bipartite matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236367)