{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T05:39:47Z","timestamp":1740807587138,"version":"3.38.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T00:00:00Z","timestamp":1737504000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T00:00:00Z","timestamp":1737504000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2127781","2127781"],"award-info":[{"award-number":["2127781","2127781"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10107-024-02178-w","type":"journal-article","created":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T15:27:16Z","timestamp":1737559636000},"page":"761-792","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Towards an optimal contention resolution scheme for matchings"],"prefix":"10.1007","volume":"210","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9423-4486","authenticated-orcid":false,"given":"Pranav","family":"Nuti","sequence":"first","affiliation":[]},{"given":"Jan","family":"Vondr\u00e1k","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,22]]},"reference":[{"key":"2178_CR1","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1007\/978-3-031-32726-1_27","volume-title":"Integer Programming and Combinatorial Optimization","author":"P Nuti","year":"2023","unstructured":"Nuti, P., Vondr\u00e1k, J.: Towards an optimal contention resolution scheme for matchings. In: Del Pia, A., Kaibel, V. (eds.) Integer Programming and Combinatorial Optimization, pp. 378\u2013392. Springer (2023)"},{"issue":"1","key":"2178_CR2","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/070680977","volume":"39","author":"U Feige","year":"2009","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput. 39(1), 122\u2013142 (2009). https:\/\/doi.org\/10.1137\/070680977","journal-title":"SIAM J. Comput."},{"issue":"6","key":"2178_CR3","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"C Chekuri","year":"2014","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014). https:\/\/doi.org\/10.1137\/110839655","journal-title":"SIAM J. Comput."},{"key":"2178_CR4","doi-asserted-by":"publisher","unstructured":"Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. 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. 1014\u20131033 (2016). https:\/\/doi.org\/10.1137\/1.9781611974331.ch72","DOI":"10.1137\/1.9781611974331.ch72"},{"key":"2178_CR5","doi-asserted-by":"publisher","unstructured":"Adamczyk, M., Wlodarczyk, M.: Random order contention resolution schemes. In: Thorup, M. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7\u20139, 2018, pp. 790\u2013801 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00080","DOI":"10.1109\/FOCS.2018.00080"},{"key":"2178_CR6","doi-asserted-by":"publisher","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, August 20\u201322, 2018, Helsinki, Finland. LIPIcs, vol. 112, pp. 57\u201315714 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.57","DOI":"10.4230\/LIPIcs.ESA.2018.57"},{"key":"2178_CR7","doi-asserted-by":"publisher","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, July 12-16, 2021, Glasgow, Scotland (Virtual Conference). LIPIcs, vol. 198, pp. 68\u201316820 (2021). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.68","DOI":"10.4230\/LIPIcs.ICALP.2021.68"},{"key":"2178_CR8","doi-asserted-by":"publisher","unstructured":"Pollner, T., Roghani, M., Saberi, A., Wajc, D.: Improved online contention resolution for matchings and applications to the gig economy. In: Proceedings of the 23rd ACM Conference on Economics and Computation. EC \u201922, pp. 321\u2013322, New York, NY, USA (2022). https:\/\/doi.org\/10.1145\/3490486.3538295","DOI":"10.1145\/3490486.3538295"},{"key":"2178_CR9","doi-asserted-by":"publisher","unstructured":"Guruganesh, G., Lee, E.: Understanding the correlation gap for matchings. In: Lokam, S.V., Ramanujam, R. (eds.) 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017, December 11\u201315, 2017, Kanpur, India. LIPIcs, vol. 93, pp. 32\u201313215 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2017.32","DOI":"10.4230\/LIPIcs.FSTTCS.2017.32"},{"issue":"2","key":"2178_CR10","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1007\/s10107-020-01570-6","volume":"191","author":"S Bruggmann","year":"2022","unstructured":"Bruggmann, S., Zenklusen, R.: An optimal monotone contention resolution scheme for bipartite matchings via a polyhedral viewpoint. Math. Program. 191(2), 795\u2013845 (2022). https:\/\/doi.org\/10.1007\/s10107-020-01570-6","journal-title":"Math. Program."},{"key":"2178_CR11","doi-asserted-by":"publisher","unstructured":"Karp, R.M., Sipser, M.: Maximum matchings in sparse random graphs. In: 22nd Annual Symposium on Foundations of Computer Science, Nashville, Tennessee, USA, 28\u201330 October 1981, pp. 364\u2013375 (1981). https:\/\/doi.org\/10.1109\/SFCS.1981.21","DOI":"10.1109\/SFCS.1981.21"},{"key":"2178_CR12","doi-asserted-by":"publisher","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 (2023). https:\/\/doi.org\/10.1137\/1.9781611977554.ch76","DOI":"10.1137\/1.9781611977554.ch76"},{"key":"2178_CR13","doi-asserted-by":"publisher","unstructured":"Balister, P., Gerke, S.: In: Czumaj, A., Georgakopoulos, A., Kr\u00e1l, D., Lozin, V., Pikhurko, O. (eds.) Controllability and Matchings in Random Bipartite Graphs. London Mathematical Society Lecture Note Series, pp. 119\u2013146 (2015). https:\/\/doi.org\/10.1017\/CBO9781316106853.004","DOI":"10.1017\/CBO9781316106853.004"},{"issue":"1","key":"2178_CR14","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00440-012-0453-0","volume":"157","author":"C Bordenave","year":"2013","unstructured":"Bordenave, C., Lelarge, M., Salez, J.: Matchings on infinite graphs. Probab. Theory Relat. Fields 157(1), 183\u2013208 (2013). https:\/\/doi.org\/10.1007\/s00440-012-0453-0","journal-title":"Probab. Theory Relat. Fields"},{"issue":"3","key":"2178_CR15","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1016\/0001-8708(81)90044-X","volume":"42","author":"GP Egorychev","year":"1981","unstructured":"Egorychev, G.P.: The solution of van der Waerden\u2019s problem for permanents. Adv. Math. 42(3), 299\u2013305 (1981). https:\/\/doi.org\/10.1016\/0001-8708(81)90044-X","journal-title":"Adv. Math."},{"issue":"10","key":"2178_CR16","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1016\/0898-1221(96)00048-X","volume":"31","author":"B Gyires","year":"1996","unstructured":"Gyires, B.: Elementary proof for Van der Waerden\u2019s conjecture and related theorems. Comput. Math. Appl. 31(10), 7\u201321 (1996)","journal-title":"Comput. Math. Appl."},{"issue":"3","key":"2178_CR17","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1017\/S0963548307008474","volume":"16","author":"J Kahn","year":"2007","unstructured":"Kahn, J., Kalai, G.: Thresholds and expectation thresholds. Combin. Probab. Comput. 16(3), 495\u2013502 (2007). https:\/\/doi.org\/10.1017\/S0963548307008474","journal-title":"Combin. Probab. Comput."},{"key":"2178_CR18","doi-asserted-by":"publisher","unstructured":"Park, J., Pham, H.T.: A proof of the Kahn\u2013Kalai conjecture. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 636\u2013639 (2022). https:\/\/doi.org\/10.1109\/FOCS54457.2022.00066","DOI":"10.1109\/FOCS54457.2022.00066"},{"key":"2178_CR19","volume-title":"The Theory of Branching Process","author":"TE Harris","year":"1964","unstructured":"Harris, T.E.: The Theory of Branching Process. RAND Corporation, Santa Monica (1964)"},{"key":"2178_CR20","unstructured":"Chekuri, C.: Personal communication"},{"issue":"2","key":"2178_CR21","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF01651330","volume":"22","author":"CM Fortuin","year":"1971","unstructured":"Fortuin, C.M., Ginibre, J., Kasteleyn, P.W.: Correlation inequalities on some partially ordered sets. Commun. Math. Phys. 22(2), 89\u2013103 (1971)","journal-title":"Commun. Math. Phys."},{"issue":"4","key":"2178_CR22","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1287\/moor.1100.0463","volume":"35","author":"J Lee","year":"2010","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4), 795\u2013806 (2010). https:\/\/doi.org\/10.1287\/moor.1100.0463","journal-title":"Math. Oper. Res."},{"issue":"1","key":"2178_CR23","doi-asserted-by":"publisher","first-page":"247","DOI":"10.4086\/toc.2010.v006a011","volume":"6","author":"U Feige","year":"2010","unstructured":"Feige, U., Vondr\u00e1k, J.: The submodular welfare problem with demand queries. Theory Comput. 6(1), 247\u2013290 (2010). https:\/\/doi.org\/10.4086\/toc.2010.v006a011","journal-title":"Theory Comput."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02178-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02178-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02178-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T16:02:01Z","timestamp":1740758521000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02178-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,22]]},"references-count":23,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["2178"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02178-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2025,1,22]]},"assertion":[{"value":"1 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 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":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"Not applicable.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}