{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T07:40:49Z","timestamp":1764574849801,"version":"3.46.0"},"reference-count":49,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T00:00:00Z","timestamp":1735862400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T00:00:00Z","timestamp":1735862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,11]]},"DOI":"10.1007\/s10107-024-02184-y","type":"journal-article","created":{"date-parts":[[2025,1,3]],"date-time":"2025-01-03T08:05:36Z","timestamp":1735891536000},"page":"303-356","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online bipartite matching in the probe-commit model"],"prefix":"10.1007","volume":"214","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0966-4332","authenticated-orcid":false,"given":"Calum","family":"MacRury","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,3]]},"reference":[{"issue":"15","key":"2184_CR1","doi-asserted-by":"publisher","first-page":"731","DOI":"10.1016\/j.ipl.2011.05.007","volume":"111","author":"M Adamczyk","year":"2011","unstructured":"Adamczyk, M.: Improved analysis of the greedy algorithm for stochastic matching. Inf. Process. Lett. 111(15), 731\u2013737 (2011)","journal-title":"Inf. Process. Lett."},{"key":"2184_CR2","unstructured":"Adamczyk, M., Grandoni, F., Leonardi, S., Wlodarczyk, M.: When the optimum is also blind: a new perspective on universal optimization. In: ICALP (2017)"},{"key":"2184_CR3","doi-asserted-by":"crossref","unstructured":"Adamczyk, M., Grandoni, F., Mukherjee, J.: Improved approximation algorithms for stochastic matching. In: Bansal, N., Finocchi, I. (eds.) Algorithms - ESA 2015\u201423rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings, vol. 9294 of Lecture Notes in Computer Science, pp. 1\u201312. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_1"},{"issue":"3","key":"2184_CR4","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1287\/moor.2015.0766","volume":"41","author":"M Adamczyk","year":"2016","unstructured":"Adamczyk, M., Sviridenko, M., Ward, J.: Submodular stochastic probing on matroids. Math. Oper. Res. 41(3), 1022\u20131038 (2016)","journal-title":"Math. Oper. Res."},{"key":"2184_CR5","doi-asserted-by":"crossref","unstructured":"Alaei, S.., Hajiaghayi, M.T., Liaghat, V.: Online prophet-inequality matching with applications to ad allocation. In: Proceedings of the 13th ACM Conference on Electronic Commerce, EC \u201912, pp. 18\u201335, New York, NY, USA, 2012. Association for Computing Machinery (2012)","DOI":"10.1145\/2229012.2229018"},{"key":"2184_CR6","doi-asserted-by":"crossref","unstructured":"Azar, Y., Chiplunkar, A., Kaplan, H.: Prophet secretary: surpassing the 1-1\/e barrier. In: Tardos, \u00c9., Elkind, E., Vohra, R. (eds.) Proceedings of the 2018 ACM Conference on Economics and Computation, Ithaca, NY, USA, June 18\u201322, 2018, pp. 303\u2013318. ACM (2018)","DOI":"10.1145\/3219166.3219182"},{"issue":"4","key":"2184_CR7","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1007\/s00453-011-9511-8","volume":"63","author":"N Bansal","year":"2012","unstructured":"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. Algorithmica 63(4), 733\u2013762 (2012)","journal-title":"Algorithmica"},{"issue":"11","key":"2184_CR8","doi-asserted-by":"publisher","first-page":"3225","DOI":"10.1007\/s00453-017-0383-4","volume":"80","author":"A Baveja","year":"2018","unstructured":"Baveja, A., Chavan, A., Nikiforov, A., Srinivasan, A., Pan, X.: Improved bounds in stochastic matching and optimization. Algorithmica 80(11), 3225\u20133252 (2018)","journal-title":"Algorithmica"},{"key":"2184_CR9","unstructured":"Borodin, A., MacRury, C., Rakheja, A.: Prophet matching meets probing with commitment. CoRR, arxiv:abs\/2102.04325 (2021)"},{"key":"2184_CR10","unstructured":"Borodin, A., MacRury, C., Rakheja, A.: Secretary matching meets probing with commitment. In: Wootters, M., Sanit\u00e0, L. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2021), vol. 207 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 13:1\u201313:23, Dagstuhl, Germany, 2021. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"key":"2184_CR11","unstructured":"Brubach, B., Grammel, N., Ma, W., Srinivasan, A.: Follow your star: new frameworks for online stochastic matching with known and unknown patience. In: Banerjee, A., Fukumizu, K. (eds.) Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, vol. 130 of Proceedings of Machine Learning Research, pp. 2872\u20132880. PMLR, 13\u201315 Apr (2021)"},{"key":"2184_CR12","unstructured":"Brubach, B., Grammel, N., Ma, W., Srinivasan, A.: Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. In: Ranzato, M., Beygelzimer, A., Dauphin, Y.N., Liang, P., Vaughan, J.W. (eds.) Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pp. 27184\u201327195 (2021)"},{"key":"2184_CR13","unstructured":"Brubach, B., Grammel, N., Ma, W., Srinivasan, A.: Online matching frameworks under stochastic rewards, product ranking, and unknown patience. Oper. Res. (2023)"},{"key":"2184_CR14","unstructured":"Brubach, B., Grammel, N., Srinivasan, A.: Vertex-weighted online stochastic matching with patience constraints. CoRR ArXiv:abs\/1907.03963 (2019)"},{"key":"2184_CR15","unstructured":"Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: New algorithms, better bounds, and a novel model for online stochastic matching. In: 24th Annual European Symposium on Algorithms, ESA 2016, August 22\u201324, 2016, Aarhus, Denmark, pp. 24:1\u201324:16 (2016)"},{"issue":"1","key":"2184_CR16","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1007\/s00453-019-00603-7","volume":"82","author":"B Brubach","year":"2020","unstructured":"Brubach, B., Sankararaman, K.A., Srinivasan, A., Xu, P.: Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts. Algorithmica 82(1), 64\u201387 (2020)","journal-title":"Algorithmica"},{"key":"2184_CR17","doi-asserted-by":"crossref","unstructured":"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: Part I, ICALP \u201909, pp. 266\u2013278 (2009)","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"2184_CR18","doi-asserted-by":"crossref","unstructured":"Correa, J.R., Saona, R., Ziliotto, B.: Prophet secretary through blind strategies. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6\u20139, 2019, pp. 1946\u20131961 (2019)","DOI":"10.1137\/1.9781611975482.118"},{"key":"2184_CR19","doi-asserted-by":"crossref","unstructured":"Costello, K.P., Tetali, P., Tripathi, P.: Stochastic matching with commitment. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) Automata, Languages, and Programming, pp. 822\u2013833. Springer Berlin Heidelberg, Berlin (2012)","DOI":"10.1007\/978-3-642-31594-7_69"},{"key":"2184_CR20","doi-asserted-by":"crossref","unstructured":"Derakhshan, M., Farhadi, A.: Beating (1 - 1\/e)-approximation for weighted stochastic matching. In: Bansal, N., Nagarajan, V. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22\u201325, 2023, pp. 1931\u20131961. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch74"},{"key":"2184_CR21","doi-asserted-by":"crossref","unstructured":"Devanur, N.R., Jain, K., Kleinberg, R.D.: Randomized primal-dual analysis of ranking for online bipartite matching. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201913, pp. 101\u2013107, Philadelphia, PA, USA . Society for Industrial and Applied Mathematics (2013)","DOI":"10.1137\/1.9781611973105.7"},{"key":"2184_CR22","doi-asserted-by":"crossref","unstructured":"Ehsani, S., Hajiaghayi, M.T., Kesselheim, T., Singla, S.: Prophet secretary for combinatorial auctions and matroids. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201918, pp. 700\u2013714, USA. Society for Industrial and Applied Mathematics (2018)","DOI":"10.1137\/1.9781611975031.46"},{"key":"2184_CR23","doi-asserted-by":"crossref","unstructured":"Ezra, T., Feldman, M., Gravin, N., Tang, Z.G.: Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. In: Proceedings of the 21st ACM Conference on Economics and Computation, EC \u201920, pp. 769\u2013787, New York, NY, USA. Association for Computing Machinery (2020)","DOI":"10.1145\/3391403.3399513"},{"key":"2184_CR24","doi-asserted-by":"crossref","unstructured":"Fata, E., Ma, W., Simchi-Levi, D.: Multi-stage and multi-customer assortment optimization with inventory constraints. CoRR ArXiv:abs\/1908.09808 (2019)","DOI":"10.2139\/ssrn.3443109"},{"key":"2184_CR25","unstructured":"Fu, H., Tang, Z.G., Wu, H., Wu, J., Zhang, Q.: Random order vertex arrival contention resolution schemes for matching, with applications. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), vol. 198 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 68:1\u201368:20, Dagstuhl, Germany. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"key":"2184_CR26","doi-asserted-by":"crossref","unstructured":"Gamlath, B., Kale, S., Svensson, O.: Beating greedy for stochastic bipartite matching. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201919, pp. 2841\u20132854, USA. Society for Industrial and Applied Mathematics (2019)","DOI":"10.1137\/1.9781611975482.176"},{"issue":"3","key":"2184_CR27","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1145\/1147954.1147956","volume":"53","author":"R Gandhi","year":"2006","unstructured":"Gandhi, R., Khuller, S., Parthasarathy, S., Srinivasan, A.: Dependent rounding and its applications to approximation algorithms. J. ACM 53(3), 324\u2013360 (2006)","journal-title":"J. ACM"},{"key":"2184_CR28","series-title":"Universitext","volume-title":"Understanding and Using Linear Programming","author":"B G\u00e4rtner","year":"2007","unstructured":"G\u00e4rtner, B., Matousek, J.: Understanding and Using Linear Programming. Universitext, Springer (2007)"},{"key":"2184_CR29","doi-asserted-by":"crossref","unstructured":"Goyal, V., Udwani, R.: Online matching with stochastic rewards: optimal competitive ratio via path based formulation. In: Bir\u00f3, P., Hartline, J.D., Ostrovsky, M., Procaccia, A.D. (eds.) EC \u201920: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13\u201317, 2020, pp. 791. ACM (2020)","DOI":"10.1145\/3391403.3399531"},{"key":"2184_CR30","unstructured":"Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: Goemans, M.X., Correa, J.R. (eds.) Integer Programming and Combinatorial Optimization\u201416th International Conference, IPCO 2013, Valpara\u00edso, Chile, March 18\u201320, 2013. Proceedings, vol. 7801 of Lecture Notes in Computer Science, pp. 205\u2013216. Springer (2013)"},{"key":"2184_CR31","unstructured":"Gupta, A., Nagarajan, V., Singla, S.: Algorithms and adaptivity gaps for stochastic probing. In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1731\u20131747. SIAM (2016)"},{"key":"2184_CR32","doi-asserted-by":"crossref","unstructured":"Huang, Z., Shu, X., Yan, S.: The power of multiple choices in online stochastic matching (2022)","DOI":"10.1145\/3519935.3520046"},{"key":"2184_CR33","doi-asserted-by":"crossref","unstructured":"Huang, Z., Zhang, Q.: Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pp. 1153\u20131164, New York, NY, USA, 2020. Association for Computing Machinery (2020)","DOI":"10.1145\/3357713.3384294"},{"key":"2184_CR34","doi-asserted-by":"crossref","unstructured":"Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13\u201317, 1990, Baltimore, Maryland, USA, pp. 352\u2013358 (1990)","DOI":"10.1145\/100216.100262"},{"key":"2184_CR35","doi-asserted-by":"crossref","unstructured":"Kesselheim, T., Radke, K., T\u00f6nnis, A., V\u00f6cking, B.: An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In: Bodlaender, H.L., Italiano, G.F. (eds.) Algorithms\u2014ESA 2013, pp. 589\u2013600. Springer Berlin Heidelberg, Berlin (2013)","DOI":"10.1007\/978-3-642-40450-4_50"},{"key":"2184_CR36","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1090\/S0002-9904-1977-14378-4","volume":"83","author":"U Krengel","year":"1977","unstructured":"Krengel, U., Sucheston, L.: Semiamarts and finite values. Bull. Am. Math. Soc. 83, 10 (1977)","journal-title":"Bull. Am. Math. Soc."},{"key":"2184_CR37","unstructured":"Lee, E.., Singla, S.: Optimal online contention resolution schemes via ex-ante prophet inequalities. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms (ESA 2018), vol. 112 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 57:1\u201357:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2018)"},{"issue":"1","key":"2184_CR38","doi-asserted-by":"publisher","first-page":"39","DOI":"10.2307\/2985407","volume":"10","author":"DV Lindley","year":"1961","unstructured":"Lindley, D.V.: Dynamic programming and decision theory. Appl. Stat. 10(1), 39\u201351 (1961)","journal-title":"Appl. Stat."},{"key":"2184_CR39","doi-asserted-by":"crossref","unstructured":"MacRury, C., Ma, W., Grammel, N.: On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. In: Bansal, N., Nagarajan, V. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, January 22\u201325, 2023, pp. 1995\u20132014. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch76"},{"issue":"4","key":"2184_CR40","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1287\/moor.1120.0551","volume":"37","author":"VH Manshadi","year":"2012","unstructured":"Manshadi, V.H., Gharan, S.O., Saberi, A.: Online stochastic matching: online actions based on offline statistics. Math. Oper. Res. 37(4), 559\u2013573 (2012)","journal-title":"Math. Oper. Res."},{"key":"2184_CR41","doi-asserted-by":"crossref","unstructured":"Mehta, A., Panigrahi, D.: Online matching with stochastic rewards. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20\u201323, 2012, pp. 728\u2013737. IEEE Computer Society (2012)","DOI":"10.1109\/FOCS.2012.65"},{"key":"2184_CR42","doi-asserted-by":"crossref","unstructured":"Mehta, A., Waggoner, B., Zadimoghaddam, M.: Online stochastic matching with unequal probabilities. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2015, pp. 1388\u20131404 10 (2015)","DOI":"10.1137\/1.9781611973730.92"},{"key":"2184_CR43","doi-asserted-by":"crossref","unstructured":"Pollner, T., Roghani, M., Saberi, A., Wajc, D.: Improved online contention resolution for matchings and applications to the gig economy. In: Pennock, D.M., Segal, I., Seuken, S. (eds.) EC \u201922: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA, July 11\u201315, 2022, pp. 321\u2013322. ACM (2022)","DOI":"10.1145\/3490486.3538295"},{"key":"2184_CR44","unstructured":"Purohit, M., Gollapudi, S., Raghavan, M.: Hiring under uncertainty. In: Chaudhuri, K., Salakhutdinov, R. (eds.) Proceedings of the 36th International Conference on Machine Learning, vol. 97 of Proceedings of Machine Learning Research, pp. 5181\u20135189. PMLR, 09\u201315 Jun (2019)"},{"key":"2184_CR45","doi-asserted-by":"crossref","unstructured":"Seese, D., Groetschel, m., lovasz, l., Schrijver, A.: Geometric algorithms and combinatorial optimization. In: Graham, R.l., Korte, B., Lovasz, l. (eds.) Algorithms and combinatorics, vol. 2. Springer-Verlag 1988, xii, 362 pp., 23 figs., dm 148,-. ISBN 3-540-13624-x. Biometr. J. 32(8):930\u2013930 (1990)","DOI":"10.1002\/bimj.4710320805"},{"key":"2184_CR46","doi-asserted-by":"crossref","unstructured":"Segev, D., Singla, S.: Efficient approximation schemes for stochastic probing and prophet problems. In: Proceedings of the 22nd ACM Conference on Economics and Computation, EC \u201921, pp. 793\u2013794, New York, NY, USA, 2021. Association for Computing Machinery (2021)","DOI":"10.1145\/3465456.3467614"},{"key":"2184_CR47","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J., Chekuri, C., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, STOC \u201911, pp. 783\u2013792, New York, NY, USA, 2011. Association for Computing Machinery (2011)","DOI":"10.1145\/1993636.1993740"},{"key":"2184_CR48","doi-asserted-by":"crossref","unstructured":"Williamson,David\u00a0P., Shmoys, David\u00a0B.: The Design of Approximation Algorithms. Cambridge University Press, USA, 1st edition (2011)","DOI":"10.1017\/CBO9780511921735"},{"key":"2184_CR49","doi-asserted-by":"crossref","unstructured":"Yan, S.: Edge-weighted online stochastic matching: Beating. In: Woodruff, D.P. (ed.) Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7\u201310, 2024, pp. 4631\u20134640. SIAM (2024)","DOI":"10.1137\/1.9781611977912.165"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02184-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02184-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02184-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T07:38:00Z","timestamp":1764574680000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02184-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,3]]},"references-count":49,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["2184"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02184-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2025,1,3]]},"assertion":[{"value":"4 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We confirm that there are no funding and\/or conflicts of interests\/competing interests regarding our submission.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}