Beating greedy for stochastic bipartite matching

DOI10.1137/1.9781611975482.176MaRDI QIDQ5236367zbMATH OpenOpenAlexFDO

Authors Buddhima Gamlath, Sagar Kale, Ola Svensson

Publication date 15 October 2019

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

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

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)

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.

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

Cited in

(8)

• Lazy Gale-Shapley for many-to-one matching with partial information
• Stochastic matching with commitment
• Fcfs infinite bipartite matching of servers and customers
• Prophet matching with general arrivals
• 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

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)