{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T03:24:50Z","timestamp":1793071490088,"version":"4.5.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T00:00:00Z","timestamp":1657584000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF Alan T. Waterman Award","award":["No. 1933331"],"award-info":[{"award-number":["No. 1933331"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,12]]},"DOI":"10.1145\/3490486.3538315","type":"proceedings-article","created":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T13:29:36Z","timestamp":1657718976000},"page":"967-985","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark"],"prefix":"10.1145","author":[{"given":"Mark","family":"Braverman","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mahsa","family":"Derakhshan","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antonio","family":"Molina Lovett","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229018"},{"key":"e_1_3_2_1_2_1","first-page":"733","article-title":"When LP Is the Cure for Your Matching Woes","volume":"63","author":"Bansal Nikhil","year":"2012","unstructured":"Nikhil Bansal , Anupam Gupta , Jian Li , Juli\u00e1n Mestre , Viswanath Nagarajan , and Atri Rudra . 2012 . When LP Is the Cure for Your Matching Woes : Improved Bounds for Stochastic Matchings. Algorithmica 63 , 4 (2012), 733 -- 762 . https:\/\/doi.org\/10.1007\/s00453-011--9511--8 10.1007\/s00453-011--9511--8 Nikhil Bansal, Anupam Gupta, Jian Li, Juli\u00e1n Mestre, Viswanath Nagarajan, and Atri Rudra. 2012. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. Algorithmica 63, 4 (2012), 733--762. https:\/\/doi.org\/10.1007\/s00453-011--9511--8","journal-title":"Improved Bounds for Stochastic Matchings. Algorithmica"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00131"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384340"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219226"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0505-7"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_23"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3331033.3331039"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_69"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1323850"},{"key":"e_1_3_2_1_11_1","volume-title":"Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models. In EC '20: The 21st ACM Conference on Economics and Computation","author":"Ezra Tomer","year":"2020","unstructured":"Tomer Ezra , Michal Feldman , Nick Gravin , and Zhihao Gavin Tang . 2020 . Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models. In EC '20: The 21st ACM Conference on Economics and Computation , Virtual Event, Hungary, July 13--17 , 2020, P\u00e9ter Bir\u00f3, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia (Eds.). ACM, 769--787. https:\/\/doi.org\/10.1145\/3391403.3399513 10.1145\/3391403.3399513 Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. 2020. Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models. In EC '20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary, July 13--17, 2020, P\u00e9ter Bir\u00f3, Jason D. Hartline, Michael Ostrovsky, and Ariel D. Procaccia (Eds.). ACM, 769--787. https:\/\/doi.org\/10.1145\/3391403.3399513"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722139"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1226130"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310611"},{"key":"e_1_3_2_1_15_1","volume-title":"Online Matching with General Arrivals. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019","author":"Gamlath Buddhima","year":"2019","unstructured":"Buddhima Gamlath , Michael Kapralov , Andreas Maggiori , Ola Svensson , and David Wajc . 2019 . Online Matching with General Arrivals. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019 , Baltimore, Maryland, USA, November 9--12 , 2019, David Zuckerman (Ed.). IEEE Computer Society, 26--37. https:\/\/doi.org\/10.1109\/FOCS.2019.00011 10.1109\/FOCS.2019.00011 Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. 2019. Online Matching with General Arrivals. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9--12, 2019, David Zuckerman (Ed.). IEEE Computer Society, 26--37. https:\/\/doi.org\/10.1109\/FOCS.2019.00011"},{"key":"e_1_3_2_1_16_1","volume-title":"Zhihao Gavin Tang, and Kangning Wang","author":"Gravin Nick","year":"2021","unstructured":"Nick Gravin , Zhihao Gavin Tang, and Kangning Wang . 2021 . Online Stochastic Matching with Edge Arrivals. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12--16, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.), Vol. 198 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 74:1--74:20. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.74 10.4230\/LIPIcs.ICALP.2021.74 Nick Gravin, Zhihao Gavin Tang, and Kangning Wang. 2021. Online Stochastic Matching with Edge Arrivals. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12--16, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.), Vol. 198. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 74:1--74:20. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.74"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329604"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22--26","author":"Hajiaghayi Mohammad Taghi","year":"2007","unstructured":"Mohammad Taghi Hajiaghayi , Robert D. Kleinberg , and Tuomas Sandholm . 2007 . Automated Online Mechanism Design and Prophet Inequalities . In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22--26 , 2007, Vancouver, British Columbia, Canada. AAAI Press, 58--65. http:\/\/www.aaai.org\/Library\/AAAI\/ 2007\/aaai07-009.php Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm. 2007. Automated Online Mechanism Design and Prophet Inequalities. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22--26, 2007, Vancouver, British Columbia, Canada. AAAI Press, 58--65. http:\/\/www.aaai.org\/Library\/AAAI\/2007\/aaai07-009.php"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17","author":"Karp Richard M.","year":"1990","unstructured":"Richard M. Karp , Umesh V. Vazirani , and Vijay V. Vazirani . 1990. An Optimal Algorithm for On-line Bipartite Matching . In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17 , 1990 , Baltimore, Maryland, USA, Harriet Ortiz (Ed.). ACM, 352--358. https:\/\/doi.org\/10.1145\/100216.100262 10.1145\/100216.100262 Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An Optimal Algorithm for On-line Bipartite Matching. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13--17, 1990, Baltimore, Maryland, USA, Harriet Ortiz (Ed.). ACM, 352--358. https:\/\/doi.org\/10.1145\/100216.100262"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"e_1_3_2_1_21_1","volume-title":"On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4","author":"Krengel Ulrich","year":"1978","unstructured":"Ulrich Krengel and Louis Sucheston . 1978. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4 ( 1978 ), 197--266. Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts, and processes with finite value. Probability on Banach spaces 4 (1978), 197--266."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"e_1_3_2_1_23_1","volume-title":"Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. In EC '21: The 22nd ACM Conference on Economics and Computation","author":"Papadimitriou Christos H.","year":"2021","unstructured":"Christos H. Papadimitriou , Tristan Pollner , Amin Saberi , and David Wajc . 2021 . Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. In EC '21: The 22nd ACM Conference on Economics and Computation , Budapest, Hungary, July 18--23 , 2021, P\u00e9ter Bir\u00f3, Shuchi Chawla, and Federico Echenique (Eds.). ACM, 763--764. https:\/\/doi.org\/10.1145\/3465456.3467613 10.1145\/3465456.3467613 Christos H. Papadimitriou, Tristan Pollner, Amin Saberi, and David Wajc. 2021. Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. In EC '21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary, July 18--23, 2021, P\u00e9ter Bir\u00f3, Shuchi Chawla, and Federico Echenique (Eds.). ACM, 763--764. https:\/\/doi.org\/10.1145\/3465456.3467613"},{"key":"e_1_3_2_1_24_1","unstructured":"Tristan Pollner. 2020. Two Problems In Combinatorial Optimization Under Uncertainty. (2020).  Tristan Pollner. 2020. Two Problems In Combinatorial Optimization Under Uncertainty. (2020)."},{"key":"e_1_3_2_1_25_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming, ICALP","author":"Saberi Amin","year":"2021","unstructured":"Amin Saberi and David Wajc . 2021. The Greedy Algorithm Is not Optimal for On-Line Edge Coloring . In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 , July 12--16, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.), Vol. 198 . Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik , 109:1--109:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.109 10.4230\/LIPIcs.ICALP.2021.109 Amin Saberi and David Wajc. 2021. The Greedy Algorithm Is not Optimal for On-Line Edge Coloring. In 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12--16, 2021, Glasgow, Scotland (Virtual Conference) (LIPIcs), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.), Vol. 198. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 109:1--109:18. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.109"},{"key":"e_1_3_2_1_26_1","volume-title":"Dynamic Relaxations for Online Bipartite Matching. arXiv preprint arXiv:1709.01557","author":"Torrico Alfredo","year":"2017","unstructured":"Alfredo Torrico and Alejandro Toriello . 2017. Dynamic Relaxations for Online Bipartite Matching. arXiv preprint arXiv:1709.01557 ( 2017 ). Alfredo Torrico and Alejandro Toriello. 2017. Dynamic Relaxations for Online Bipartite Matching. arXiv preprint arXiv:1709.01557 (2017)."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.21"}],"event":{"name":"EC '22: The 23rd ACM Conference on Economics and Computation","location":"Boulder CO USA","acronym":"EC '22","sponsor":["SIGecom Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 23rd ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490486.3538315","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3490486.3538315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:02:59Z","timestamp":1750186979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3490486.3538315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,12]]},"references-count":27,"alternative-id":["10.1145\/3490486.3538315","10.1145\/3490486"],"URL":"https:\/\/doi.org\/10.1145\/3490486.3538315","relation":{},"subject":[],"published":{"date-parts":[[2022,7,12]]},"assertion":[{"value":"2022-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}