Abstract
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 et al. (ICALP’09, LNCS, vol. 5555, pp. 266–278, [2009]).
-
We introduce a generalization of the stochastic online matching problem (Feldman et al. in FOCS’09, pp. 117–126, [2009]) that also models preference-uncertainty and timeouts of buyers, and give a constant factor approximation algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adamczyk, M.: Greedy algorithm for stochastic matching is a 2-approximation. arXiv:1007.3036 (2010)
Alon, N., Spencer, J.H.: The Probabilistic Method. Wiley-Interscience, New York (2008)
Bahmani, B., Kapralov, M.: Improved bounds for online stochastic matching. In: Proceedings of the 18th European Symposium on Algorithms. LNCS, vol. 6346, pp. 170–181. Springer, Berlin (2010)
Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. In: Proceedings of the 18th European Symposium on Algorithms. LNCS, vol. 6346, pp. 218–229. Springer, Berlin (2010)
Bansal, N., Korula, N., Nagarajan, V., Srinivasan, A.: On k-column sparse packing programs. In: Proceedings of the 14th Conference on Integer Programming and Combinatorial Optimization. LNCS, vol. 6080, pp. 369–382 (2010)
Bhattacharya, S., Goel, G., Gollapudi, S., Munagala, K.: Budget constrained auctions with heterogeneous items. In: Proceedings of the 41st ACM Symposium on Theory of Computing, pp. 379–388. ACM, New York (2010)
Birnbaum, B.E., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39(1), 80–87 (2008)
Carr, R., Vempala, S.: Randomized metarounding. Random Struct. Algorithms 20(3), 343–352 (2002). Probabilistic methods in combinatorial optimization
Chen, N., Immorlica, N., Karlin, A.R., Mahdian, M., Rudra, A.: Approximating matches made in heaven. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming. LNCS, vol. 5555, pp. 266–278 (2009)
Dean, B.C., Goemans, M.X., Vondrák, J.: Adaptivity and approximation for stochastic packing problems. In: Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 395–404 (2005)
Dean, B.C., Goemans, M.X., Vondrák, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. Math. Oper. Res. 33(4), 945–964 (2008)
Feldman, J., Mehta, A., Mirrokni, V.S., Muthukrishnan, S.: Online stochastic matching: beating 1−1/e. In: Proceedings of the 50th Annual Symposium on Foundations of Computer Science, pp. 117–126. IEEE, New York (2009)
Füredi, Z., Kahn, J., Seymour, P.: On the fractional matching polytope of a hypergraph. Combinatorica 13(2), 167–180 (1993)
Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 360 (2006)
Goel, G., Mehta, A.: Online budgeted matching in random input models with applications to adwords. In: Proceedings of the 19th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 982–991 (2008)
Guha, S., Munagala, K.: Approximation algorithms for partial-information based stochastic control with Markovian rewards. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 483–493 (2007)
Guha, S., Munagala, K.: Multi-armed bandits with metric switching costs. In: Proceedings of the 36th International Colloquium on Automata, Languages and Programming. LNCS, vol. 5555, pp. 496–507 (2009)
Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: Approximation algorithms for correlated knapsacks and non-martingale bandits. CoRR, abs/1102.3749 (2011)
Gupta, A., Pál, M., Ravi, R., Sinha, A.: Boosted sampling: approximation algorithms for stochastic optimization. In: Proceedings of the 36th ACM Symposium on Theory of Computing, pp. 417–426. ACM, New York (2004)
Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating k-set packing. Comput. Complex. 15(1), 20–39 (2006)
Hurkens, C., Schrijver, A.: On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems. SIAM J. Discrete Math. 2(1), 68–72 (1989)
Kalyanasundaram, B., Pruhs, K.: Online weighted matching. J. Algorithms 14(3), 478–488 (1993)
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for online bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pp. 352–358. ACM, New York (1990)
Katriel, I., Kenyon-Mathieu, C., Upfal, E.: Commitment under uncertainty: two-stage stochastic matching problems. Theor. Comput. Sci. 408(2–3), 213–223 (2008)
Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In: Proceedings of the 8th ACM Conference on Electronic Commerce, pp. 288–294 (2007)
Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: Online actions based on offline statistics. In: Proceedings of the 22th Annual ACM–SIAM Symposium on Discrete Algorithms (2011)
Mehta, A., Saberi, A., Vazirani, U.V., Vazirani, V.V.: Adwords and generalized on-line matching. In: Proceedings of the 46th Annual Symposium on Foundations of Computer Science, pp. 264–273 (2005)
Schrijver, A.: Combinatorial Optimization. Springer, Berlin (2003)
Shachnai, H., Srinivasan, A.: Finding large independent sets in graphs and hypergraphs. SIAM J. Discrete Math. 18(3), 488–500 (2005)
Shmoys, D., Swamy, C.: An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6), 978–1012 (2006)
Swamy, C., Shmoys, D.: Approximation algorithms for 2-stage stochastic optimization problems. SIGACT News 37(1), 46 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
A. Gupta was supported in part by NSF awards CCF-0729022 and CCF-1016799, and an Alfred P. Sloan Fellowship.
A. Rudra was supported by NSF CAREER award CCF-0844796.
Rights and permissions
About this article
Cite this article
Bansal, N., Gupta, A., Li, J. et al. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica 63, 733–762 (2012). https://doi.org/10.1007/s00453-011-9511-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9511-8