{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:39:00Z","timestamp":1782970740291,"version":"3.54.5"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,8,31]],"date-time":"2019-08-31T00:00:00Z","timestamp":1567209600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1116961, CCF-1552909, and IIS-1447470"],"award-info":[{"award-number":["CCF-1116961, CCF-1552909, and IIS-1447470"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2019,8,31]]},"abstract":"\n Motivated by an application in\n kidney exchange<\/jats:italic>\n , we study the following\n stochastic matching<\/jats:italic>\n problem: We are given a graph\n G<\/jats:italic>\n (\n V, E<\/jats:italic>\n ) (not necessarily bipartite), where each edge in\n E<\/jats:italic>\n is\n realized<\/jats:italic>\n with some constant probability\n p<\/jats:italic>\n > 0, and the goal is to find a maximum matching in the realized graph. An algorithm in this setting is allowed to make\n queries<\/jats:italic>\n to edges in\n E<\/jats:italic>\n to determine whether or not they are realized.\n <\/jats:p>\n \n We design an\n adaptive<\/jats:italic>\n algorithm for this problem that, for any graph\n G<\/jats:italic>\n , computes a (1\u2212\u03b5)-approximate maximum matching in the realized graph\n G<\/jats:italic>\n \n p<\/jats:italic>\n <\/jats:sub>\n with high probability, while making\n O<\/jats:italic>\n (log (1\/\u03b5\n p<\/jats:italic>\n )\/\u03b5\n p<\/jats:italic>\n ) queries per vertex, where the edges to query are chosen adaptively in\n O<\/jats:italic>\n (log (1\/\u03b5\n p<\/jats:italic>\n )\/\u03b5\n p<\/jats:italic>\n ) rounds. We further present a\n non-adaptive<\/jats:italic>\n algorithm that makes\n O<\/jats:italic>\n (log (1\/\u03b5\n p<\/jats:italic>\n )\/\u03b5\n p<\/jats:italic>\n ) queries per vertex and computes a (1\/2\u2212\u03b5)-approximate maximum matching in\n G<\/jats:italic>\n \n p<\/jats:italic>\n <\/jats:sub>\n with high probability.\n <\/jats:p>\n \n Both our adaptive and non-adaptive algorithms achieve the same approximation factor as the previous best algorithms of Blum et\u00a0al. (EC 2015) for this problem, while requiring an\n exponentially smaller<\/jats:italic>\n number of per-vertex queries (and rounds of adaptive queries for the adaptive algorithm). Our results settle an open problem raised by Blum et\u00a0al. by achieving only a polynomial dependency on both \u03b5 and\n p<\/jats:italic>\n . Moreover, the approximation guarantee of our algorithms is\n instance-wise<\/jats:italic>\n as opposed to only being competitive in\n expectation<\/jats:italic>\n as is the case for Blum et\u00a0al. This is of particular relevance to the key application of stochastic matching in kidney exchange. We obtain our results via two main techniques\u2014namely,\n matching-covers<\/jats:italic>\n and\n vertex sparsification<\/jats:italic>\n \u2014that may be of independent interest.\n <\/jats:p>","DOI":"10.1145\/3355903","type":"journal-article","created":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T12:58:26Z","timestamp":1569329906000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["The Stochastic Matching Problem with (Very) Few Queries"],"prefix":"10.1145","volume":"7","author":[{"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yang","family":"Li","sequence":"additional","affiliation":[{"name":"University of Pennsylvania"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,9,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.05.007"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600057.2602887"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.129"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1421853112"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.102.3.354"},{"key":"e_1_2_1_6_1","unstructured":"Sepehr Assadi and Aaron Bernstein. 2018. Towards a unified theory of sparsification for matching problems. Retrieved from: CoRR abs\/1811.02009 (2018). Sepehr Assadi and Aaron Bernstein. 2018. Towards a unified theory of sparsification for matching problems. Retrieved from: CoRR abs\/1811.02009 (2018)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2940716.2940769"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3033274.3085146"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch93"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI\u201909)","author":"Awasthi Pranjal","year":"2009"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/2220253.2220257"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219226"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764479"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482569"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch92"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_69"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 26th AAAI Conference on Artificial Intelligence.","author":"Dickerson John P.","year":"2012"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492002.2482596"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 29th AAAI Conference on Artificial Intelligence.622--628","author":"John"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_2_1_22_1","unstructured":"National Kidney Foundation. 2016. Organ Donation and Transplantation Statistics. Retrieved from: https:\/\/www.kidney.org\/news\/newsroom\/factsheets\/Organ-Donation-and-Transplantation-Stats. National Kidney Foundation. 2016. Organ Donation and Transplantation Statistics. Retrieved from: https:\/\/www.kidney.org\/news\/newsroom\/factsheets\/Organ-Donation-and-Transplantation-Stats."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36694-9_18"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz and D. Plummer. 2009. Matching Theory. American Mathematical Society. Retrieved from: https:\/\/books.google.com\/books?id=yW3WSVq8ygcC. L. Lov\u00e1sz and D. Plummer. 2009. Matching Theory. American Mathematical Society. Retrieved from: https:\/\/books.google.com\/books?id=yW3WSVq8ygcC.","DOI":"10.1090\/chel\/367"},{"key":"e_1_2_1_26_1","article-title":"Paired and altruistic kidney donation in the UK: Algorithms and experimentation","volume":"19","author":"Manlove David F.","year":"2014","journal-title":"ACM J. Exper. Algor."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1162\/0033553041382157"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.04.004"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1257\/aer.97.3.828"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-937X.2009.00575.x"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.21"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355903","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355903","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3355903","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:13:30Z","timestamp":1750202010000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3355903"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,31]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3355903"],"URL":"https:\/\/doi.org\/10.1145\/3355903","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,31]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}