{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T18:32:09Z","timestamp":1772649129220,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","funder":[{"name":"NSFC grant","award":["No. 6212290003"],"award-info":[{"award-number":["No. 6212290003"]}]},{"name":"National Key R&D Program of China","award":["2023YFA1009500"],"award-info":[{"award-number":["2023YFA1009500"]}]},{"name":"NSF awards","award":["CCF-2327010, CCF-2440113"],"award-info":[{"award-number":["CCF-2327010, CCF-2440113"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718196","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"1430-1441","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Stochastic Matching with Unknown Arrival Order: Beating 0.5 against the Online Optimum"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5627-7900","authenticated-orcid":false,"given":"Enze","family":"Sun","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5094-1971","authenticated-orcid":false,"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"Shanghai University of Finance and Economics, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5117-5706","authenticated-orcid":false,"given":"Yifan","family":"Wang","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055479"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3391403.3399484"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219182"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1287\/OPRE.2021.2121"},{"key":"e_1_3_2_1_5_1","volume-title":"Multiway Online Correlated Selection","author":"Blanc Guy","unstructured":"Guy Blanc and Moses Charikar. 2021. Multiway Online Correlated Selection. In FOCS. IEEE, 1277\u20131284."},{"key":"e_1_3_2_1_6_1","volume-title":"Approximating Optimum Online for Capacitated Resource Allocation. CoRR, abs\/2406.07757","author":"Braun Alexander","year":"2024","unstructured":"Alexander Braun, Thomas Kesselheim, Tristan Pollner, and Amin Saberi. 2024. Approximating Optimum Online for Capacitated Resource Allocation. CoRR, abs\/2406.07757 (2024)."},{"key":"e_1_3_2_1_7_1","volume-title":"Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. In ACM Conference on Economics and Computation, EC.","author":"Braverman Mark","year":"2022","unstructured":"Mark Braverman, Mahsa Derakhshan, and Antonio Molina Lovett. 2022. Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. In ACM Conference on Economics and Computation, EC."},{"key":"e_1_3_2_1_8_1","volume-title":"New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. CoRR, abs\/2407.15285","author":"Braverman Mark","year":"2024","unstructured":"Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, and David Wajc. 2024. New Philosopher Inequalities for Online Bayesian Matching, via Pivotal Sampling. CoRR, abs\/2407.15285 (2024)."},{"key":"e_1_3_2_1_9_1","unstructured":"Brian Brubach Nathaniel Grammel Will Ma and Aravind Srinivasan. 2021. Improved Guarantees for Offline Stochastic Matching via new Ordered Contention Resolution Schemes. In NeurIPS. 27184\u201327195."},{"key":"e_1_3_2_1_10_1","volume-title":"Prophet Inequality: Order selection beats random order. In EC. ACM, 302\u2013336.","author":"Bubna Archit","year":"2023","unstructured":"Archit Bubna and Ashish Chiplunkar. 2023. Prophet Inequality: Order selection beats random order. In EC. ACM, 302\u2013336."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806733"},{"key":"e_1_3_2_1_12_1","volume-title":"Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection. CoRR, abs\/2406.15192","author":"Chen Liyan","year":"2024","unstructured":"Liyan Chen, Nuozhou Sun, and Zhihao Gavin Tang. 2024. Setting Targets is All You Need:Improved Order Competitive Ratio for Online Selection. CoRR, abs\/2406.15192 (2024)."},{"key":"e_1_3_2_1_13_1","volume-title":"Stochastic Online Correlated Selection. CoRR, abs\/2408.12524","author":"Chen Ziyun","year":"2024","unstructured":"Ziyun Chen, Zhiyi Huang, and Enze Sun. 2024. Stochastic Online Correlated Selection. CoRR, abs\/2408.12524 (2024)."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585151"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.2020.1105"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10107-020-01544-8"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-71033-9_23"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.56"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00037"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.46"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649786"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1029394"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.2021.1152"},{"key":"e_1_3_2_1_24_1","volume-title":"SODA","author":"Ezra Tomer","unstructured":"Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. 2023. \"Who is Next in Line?\" On the Significance of Knowing the Arrival Order in Bayesian Online Settings. In SODA. SIAM, 3759\u20133776."},{"key":"e_1_3_2_1_25_1","volume-title":"Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms. CoRR, abs\/2402.17160","author":"Ezra Tomer","year":"2024","unstructured":"Tomer Ezra, Michal Feldman, and Zhihao Gavin Tang. 2024. Choosing Behind the Veil: Tight Bounds for Identity-Blind Online Algorithms. CoRR, abs\/2402.17160 (2024)."},{"key":"e_1_3_2_1_26_1","volume-title":"WINE (Lecture Notes in Computer Science","volume":"271","author":"Ezra Tomer","year":"2023","unstructured":"Tomer Ezra and Tamar Garbuz. 2023. The Importance of Knowing the Arrival Order in Combinatorial Bayesian Settings. In WINE (Lecture Notes in Computer Science, Vol. 14413). Springer, 256\u2013271."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3556971"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_34"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Jon Feldman Aranyak Mehta Vahab S. Mirrokni and S. Muthukrishnan. 2009. Online Stochastic Matching: Beating 1-1\/e. In FOCS. IEEE Computer Society 117\u2013126.","DOI":"10.1109\/FOCS.2009.72"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722139"},{"key":"e_1_3_2_1_31_1","volume-title":"Improved Online Correlated Selection","author":"Gao Ruiquan","unstructured":"Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong. 2021. Improved Online Correlated Selection. In FOCS. IEEE, 1265\u20131276."},{"key":"e_1_3_2_1_32_1","volume-title":"New Prophet Inequalities via Poissonization and Sharding. CoRR, abs\/2307.00971","author":"Harb Elfarouk","year":"2023","unstructured":"Elfarouk Harb. 2023. New Prophet Inequalities via Poissonization and Sharding. CoRR, abs\/2307.00971 (2023)."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Zhiyi Huang and Xinkai Shu. 2021. Online stochastic matching poisson arrivals and the natural linear program. In STOC. ACM 682\u2013693.","DOI":"10.1145\/3406325.3451079"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Zhiyi Huang Xinkai Shu and Shuyi Yan. 2022. The power of multiple choices in online stochastic matching. In STOC. ACM 91\u2013103.","DOI":"10.1145\/3519935.3520046"},{"key":"e_1_3_2_1_36_1","volume-title":"Zhihao Gavin Tang, and David Wajc","author":"Huang Zhiyi","year":"2024","unstructured":"Zhiyi Huang, Zhihao Gavin Tang, and David Wajc. 2024. Online Matching: A Brief Survey. CoRR, abs\/2407.05381 (2024)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1977-14378-4"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0095646"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2408.07616"},{"key":"e_1_3_2_1_43_1","volume-title":"Online Dependent Rounding Schemes. CoRR, abs\/2301.08680","author":"Naor Joseph","year":"2023","unstructured":"Joseph Naor, Aravind Srinivasan, and David Wajc. 2023. Online Dependent Rounding Schemes. CoRR, abs\/2301.08680 (2023)."},{"key":"e_1_3_2_1_44_1","volume-title":"Approximating Optimum Online. In WINE (Lecture Notes in Computer Science","volume":"374","author":"Niazadeh Rad","year":"2018","unstructured":"Rad Niazadeh, Amin Saberi, and Ali Shameli. 2018. Prophet Inequalities vs. Approximating Optimum Online. In WINE (Lecture Notes in Computer Science, Vol. 11316). Springer, 356\u2013374."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1287\/MOOR.2023.1389"},{"key":"e_1_3_2_1_46_1","volume-title":"Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design","author":"Peng Bo","unstructured":"Bo Peng and Zhihao Gavin Tang. 2022. Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design. In FOCS. IEEE, 171\u2013178."},{"key":"e_1_3_2_1_47_1","volume-title":"WINE (Lecture Notes in Computer Science","volume":"544","author":"Qiu Guoliang","year":"2023","unstructured":"Guoliang Qiu, Yilong Feng, Shengwei Zhou, and Xiaowei Wu. 2023. Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching. In WINE (Lecture Notes in Computer Science, Vol. 14413). Springer, 527\u2013544."},{"key":"e_1_3_2_1_48_1","first-page":"1","article-title":"The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. In ICALP (LIPIcs, Vol. 198)","volume":"109","author":"Saberi Amin","year":"2021","unstructured":"Amin Saberi and David Wajc. 2021. The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. In ICALP (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 109:1\u2013109:18.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","unstructured":"Ester Samuel-Cahn. 1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability 1213\u20131216. https:\/\/doi.org\/10.1214\/aop\/1176993229 10.1214\/aop\/1176993229","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Zhihao Gavin Tang Jinzhao Wu and Hongxun Wu. 2022. (Fractional) online stochastic matching via fine-grained offline statistics. In STOC. ACM 77\u201390.","DOI":"10.1145\/3519935.3519994"},{"key":"e_1_3_2_1_51_1","volume-title":"Edge-weighted Online Stochastic Matching: Beating 1-1\/e","author":"Yan Shuyi","unstructured":"Shuyi Yan. 2024. Edge-weighted Online Stochastic Matching: Beating 1-1\/e. In SODA. SIAM, 4631\u20134640."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:43:15Z","timestamp":1750693395000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":51,"alternative-id":["10.1145\/3717823.3718196","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718196","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}