{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:57:44Z","timestamp":1781078264029,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T00:00:00Z","timestamp":1594598400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel Science Foundation","award":["317\/17"],"award-info":[{"award-number":["317\/17"]}]},{"name":"National Natural Science Foundation of China","award":["61902233"],"award-info":[{"award-number":["61902233"]}]},{"name":"Science and Technology Innovation 2030","award":["2018AAA0100903"],"award-info":[{"award-number":["2018AAA0100903"]}]},{"name":"European Research Council","award":["866132"],"award-info":[{"award-number":["866132"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,7,13]]},"DOI":"10.1145\/3391403.3399513","type":"proceedings-article","created":{"date-parts":[[2020,7,9]],"date-time":"2020-07-09T16:00:25Z","timestamp":1594310425000},"page":"769-787","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Online Stochastic Max-Weight Matching: Prophet Inequality for Vertex and Edge Arrival Models"],"prefix":"10.1145","author":[{"given":"Tomer","family":"Ezra","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Feldman","sequence":"additional","affiliation":[{"name":"Tel Aviv University & Microsoft Research, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nick","family":"Gravin","sequence":"additional","affiliation":[{"name":"ITCS, Shanghai University of Finance and Economics, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"ITCS, Shanghai University of Finance and Economics, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,7,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Random Order Contention Resolution Schemes","author":"Adamczyk Marek","unstructured":"Marek Adamczyk and Michal Wlodarczyk . 2018. Random Order Contention Resolution Schemes . In FOCS. IEEE Computer Society , 790--801. Marek Adamczyk and Michal Wlodarczyk. 2018. Random Order Contention Resolution Schemes. In FOCS. IEEE Computer Society, 790--801."},{"key":"e_1_3_2_1_2_1","volume-title":"Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers","author":"Alaei Saeed","unstructured":"Saeed Alaei . 2011. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers . In FOCS. IEEE Computer Society , 512--521. Saeed Alaei. 2011. Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. In FOCS. IEEE Computer Society, 512--521."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Saeed Alaei MohammadTaghi Hajiaghayi and Vahid Liaghat. 2012. Online prophet-inequality matching with applications to ad allocation. In EC. ACM 18--35.  Saeed Alaei MohammadTaghi Hajiaghayi and Vahid Liaghat. 2012. Online prophet-inequality matching with applications to ad allocation. In EC. ACM 18--35.","DOI":"10.1145\/2229012.2229018"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Itai Ashlagi Maximilien Burq Chinmoy Dutta Patrick Jaillet Amin Saberi and Chris Sholley. 2019. Edge Weighted Online Windowed Matching. InEC. ACM 729--742.  Itai Ashlagi Maximilien Burq Chinmoy Dutta Patrick Jaillet Amin Saberi and Chris Sholley. 2019. Edge Weighted Online Windowed Matching. InEC. ACM 729--742.","DOI":"10.1145\/3328526.3329573"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.100"},{"key":"e_1_3_2_1_6_1","volume-title":"An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint. CoRRabs\/1905.08658","author":"Bruggmann Simon","year":"2019","unstructured":"Simon Bruggmann and Rico Zenklusen . 2019. An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint. CoRRabs\/1905.08658 ( 2019 ). Simon Bruggmann and Rico Zenklusen. 2019. An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint. CoRRabs\/1905.08658 (2019)."},{"key":"e_1_3_2_1_7_1","volume-title":"Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. InESA (Lecture Notes in Computer Science)","author":"Buchbinder Niv","unstructured":"Niv Buchbinder , Kamal Jain , and Joseph Naor . 2007. Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. InESA (Lecture Notes in Computer Science) , Vol. 4698 . Springer , 253--264. Niv Buchbinder, Kamal Jain, and Joseph Naor. 2007. Online Primal-Dual Algorithms for Maximizing Ad-Auctions Revenue. InESA (Lecture Notes in Computer Science), Vol. 4698. Springer, 253--264."},{"key":"e_1_3_2_1_8_1","volume-title":"Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. In 25th Annual European Symposium on Algorithms, ESA 2017","author":"Buchbinder Niv","year":"2017","unstructured":"Niv Buchbinder , Danny Segev , and Yevgeny Tkach . 2017 . Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. In 25th Annual European Symposium on Algorithms, ESA 2017 , September 4 --6 , 2017, Vienna, Austria.22:1--22:14. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.22 10.4230\/LIPIcs.ESA.2017.22 Niv Buchbinder, Danny Segev, and Yevgeny Tkach. 2017. Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4--6, 2017, Vienna, Austria.22:1--22:14. https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2017.22"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Shuchi Chawla Jason D. Hartline David L. Malec and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In STOC. ACM 311--320.  Shuchi Chawla Jason D. Hartline David L. Malec and Balasubramanian Sivan. 2010. Multi-parameter mechanism design and sequential posted pricing. In STOC. ACM 311--320.","DOI":"10.1145\/1807406.1807428"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329627"},{"key":"e_1_3_2_1_12_1","volume-title":"The Two-Sided Game of Googol and Sample-Based Prophet Inequalities","author":"Correa Jos\u00e9 R","year":"2066","unstructured":"Jos\u00e9 R Correa , Andr\u00e9s Cristi , Boris Epstein , and Jos\u00e9 A Soto . 2020. The Two-Sided Game of Googol and Sample-Based Prophet Inequalities . InSODA. SIAM , 2066 --2081. Jos\u00e9 R Correa, Andr\u00e9s Cristi, Boris Epstein, and Jos\u00e9 A Soto. 2020. The Two-Sided Game of Googol and Sample-Based Prophet Inequalities. InSODA. SIAM, 2066--2081."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_69"},{"key":"e_1_3_2_1_14_1","volume-title":"Devanur and Kamal Jain","author":"Nikhil","year":"2012","unstructured":"Nikhil R. Devanur and Kamal Jain . 2012 . Online matching with concave returns. InSTOC. ACM , 137--144. Nikhil R. Devanur and Kamal Jain. 2012. Online matching with concave returns. InSTOC. ACM, 137--144."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3284177"},{"key":"e_1_3_2_1_16_1","volume-title":"Prophet Inequalities Made Easy:Stochastic Optimization by Pricing Non-Stochastic Inputs","author":"Duetting Paul","unstructured":"Paul Duetting , Michal Feldman , Thomas Kesselheim , and Brendan Lucier . 2017. Prophet Inequalities Made Easy:Stochastic Optimization by Pricing Non-Stochastic Inputs . In FOCS. IEEE Computer Society , 540--551. Paul Duetting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier. 2017. Prophet Inequalities Made Easy:Stochastic Optimization by Pricing Non-Stochastic Inputs. In FOCS. IEEE Computer Society, 540--551."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_37"},{"key":"e_1_3_2_1_18_1","volume-title":"An Economic-Based Analysis of RANKING for Online Bipartite Matching. CoRRabs\/1804.06637","author":"Eden Alon","year":"2018","unstructured":"Alon Eden , Michal Feldman , Amos Fiat , and Kineret Segal . 2018. An Economic-Based Analysis of RANKING for Online Bipartite Matching. CoRRabs\/1804.06637 ( 2018 ). Alon Eden, Michal Feldman, Amos Fiat, and Kineret Segal. 2018. An Economic-Based Analysis of RANKING for Online Bipartite Matching. CoRRabs\/1804.06637 (2018)."},{"key":"e_1_3_2_1_19_1","volume-title":"Prophet Secretary for Combinatorial Auctions and Matroids","author":"Ehsani Soheil","unstructured":"Soheil Ehsani , MohammadTaghi Hajiaghayi , Thomas Kesselheim , and Sahil Singla . 2018. Prophet Secretary for Combinatorial Auctions and Matroids . In SODA. SIAM , 700--714. Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla. 2018. Prophet Secretary for Combinatorial Auctions and Matroids. In SODA. SIAM, 700--714."},{"key":"e_1_3_2_1_20_1","volume-title":"Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models. CoRRabs\/2002.09807","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. CoRRabs\/2002.09807 ( 2020 ). Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. 2020. Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models. CoRRabs\/2002.09807 (2020)."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219211"},{"key":"e_1_3_2_1_22_1","volume-title":"Combinatorial Auctions via Posted Prices","author":"Feldman Michal","unstructured":"Michal Feldman , Nick Gravin , and Brendan Lucier . 2015. Combinatorial Auctions via Posted Prices . In SODA. SIAM ,123--135. Michal Feldman, Nick Gravin, and Brendan Lucier. 2015. Combinatorial Auctions via Posted Prices. In SODA. SIAM,123--135."},{"key":"e_1_3_2_1_23_1","volume-title":"A Unified Continuous Greedy Algorithm for Submodular Maximization","author":"Feldman Moran","unstructured":"Moran Feldman , Joseph Naor , and Roy Schwartz . 2011. A Unified Continuous Greedy Algorithm for Submodular Maximization . In FOCS. IEEE Computer Society , 570--579. Moran Feldman, Joseph Naor, and Roy Schwartz. 2011. A Unified Continuous Greedy Algorithm for Submodular Maximization. In FOCS. IEEE Computer Society, 570--579."},{"key":"e_1_3_2_1_24_1","volume-title":"Online Contention Resolution Schemes","author":"Feldman Moran","unstructured":"Moran Feldman , Ola Svensson , and Rico Zenklusen . 2016. Online Contention Resolution Schemes . In SODA. SIAM ,1014--1033. Moran Feldman, Ola Svensson, and Rico Zenklusen. 2016. Online Contention Resolution Schemes. In SODA. SIAM,1014--1033."},{"key":"e_1_3_2_1_25_1","volume-title":"Beating Greedy for Stochastic Bipartite Matching","author":"Gamlath Buddhima","unstructured":"Buddhima Gamlath , Sagar Kale , and Ola Svensson . 2019. Beating Greedy for Stochastic Bipartite Matching . In SODA. SIAM , 2841--2854. Buddhima Gamlath, Sagar Kale, and Ola Svensson. 2019. Beating Greedy for Stochastic Bipartite Matching. In SODA. SIAM, 2841--2854."},{"key":"e_1_3_2_1_26_1","volume-title":"Online Matching with General Arrivals","author":"Gamlath Buddhima","unstructured":"Buddhima Gamlath , Michael Kapralov , Andreas Maggiori , Ola Svensson , and David Wajc . 2019. Online Matching with General Arrivals . In FOCS. IEEE Computer Society , 26--37. Buddhima Gamlath, Michael Kapralov, Andreas Maggiori, Ola Svensson, and David Wajc. 2019. Online Matching with General Arrivals. In FOCS. IEEE Computer Society, 26--37."},{"key":"e_1_3_2_1_27_1","volume-title":"Zhihao Gavin Tang, and Kangning Wang","author":"Gravin Nick","year":"2019","unstructured":"Nick Gravin , Zhihao Gavin Tang, and Kangning Wang . 2019 . Online Stochastic Matching with Edge Arrivals. CoRRabs\/ 1911.04686 (2019). Nick Gravin, Zhihao Gavin Tang, and Kangning Wang. 2019. Online Stochastic Matching with Edge Arrivals. CoRRabs\/1911.04686 (2019)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329604"},{"key":"e_1_3_2_1_29_1","volume-title":"FSTTCS (LIPIcs)","volume":"93","author":"Guruganesh Guru","year":"2017","unstructured":"Guru Guruganesh and Euiwoong Lee . 2017 . Understanding the Correlation Gap For Matchings . In FSTTCS (LIPIcs) , Vol. 93 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 32:1--32:15. Guru Guruganesh and Euiwoong Lee. 2017. Understanding the Correlation Gap For Matchings. In FSTTCS (LIPIcs), Vol. 93. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 32:1--32:15."},{"key":"e_1_3_2_1_30_1","volume-title":"Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence. 58--65","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. 58--65 . 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. 58--65."},{"key":"e_1_3_2_1_31_1","volume-title":"Xiaowei Wu, Yuhao Zhang, and Xue Zhu.","author":"Huang Zhiyi","year":"2018","unstructured":"Zhiyi Huang , Ning Kang , Zhihao Gavin Tang , Xiaowei Wu, Yuhao Zhang, and Xue Zhu. 2018 . How to match when all vertices arrive online. In STOC. ACM , 17--29. Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. 2018. How to match when all vertices arrive online. In STOC. ACM, 17--29."},{"key":"e_1_3_2_1_32_1","volume-title":"Runzhou Tao, Xiaowei Wu, and Yuhao Zhang.","author":"Huang Zhiyi","year":"2019","unstructured":"Zhiyi Huang , Binghui Peng , Zhihao Gavin Tang , Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. 2019 . Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model. In SODA. SIAM , 2875--2886. Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. 2019. Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model. In SODA. SIAM, 2875--2886."},{"key":"e_1_3_2_1_33_1","volume-title":"Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, STOC. ACM, 352--358","author":"Karp Richard M.","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, STOC. ACM, 352--358 . 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, STOC. ACM, 352--358."},{"key":"e_1_3_2_1_34_1","unstructured":"Douglas P Kennedy. 1985. Optimal stopping of independent random variables and maximizing prophets. The Annals of Probability(1985) 566--571.  Douglas P Kennedy. 1985. Optimal stopping of independent random variables and maximizing prophets. The Annals of Probability(1985) 566--571."},{"key":"e_1_3_2_1_35_1","volume-title":"Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their applications 24, 1","author":"Kennedy Douglas P","year":"1987","unstructured":"Douglas P Kennedy . 1987. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their applications 24, 1 ( 1987 ), 77--88. Douglas P Kennedy. 1987. Prophet-type inequalities for multi-choice optimal stopping. Stochastic Processes and their applications 24, 1 (1987), 77--88."},{"key":"e_1_3_2_1_36_1","volume-title":"Comparison of optimal value and constrained maxima expectations for independent random variables. Advances in applied probability 18, 2","author":"Kertz Robert P","year":"1986","unstructured":"Robert P Kertz . 1986. Comparison of optimal value and constrained maxima expectations for independent random variables. Advances in applied probability 18, 2 ( 1986 ), 311--340. Robert P Kertz. 1986. Comparison of optimal value and constrained maxima expectations for independent random variables. Advances in applied probability 18, 2 (1986), 311--340."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2014.11.002"},{"key":"e_1_3_2_1_38_1","volume-title":"Semiamarts and finite values. Bull. Amer. Math. Soc.83, 4 (07","author":"Krengel Ulrich","year":"1977","unstructured":"Ulrich Krengel and Louis Sucheston . 1977. Semiamarts and finite values. Bull. Amer. Math. Soc.83, 4 (07 1977 ), 745--747. Ulrich Krengel and Louis Sucheston. 1977. Semiamarts and finite values. Bull. Amer. Math. Soc.83, 4 (07 1977), 745--747."},{"key":"e_1_3_2_1_39_1","volume-title":"On semiamarts, amarts, and processes with finite value.Advances in Prob 4,197--266","author":"Krengel Ulrich","year":"1978","unstructured":"Ulrich Krengel and Louis Sucheston . 1978. On semiamarts, amarts, and processes with finite value.Advances in Prob 4,197--266 ( 1978 ), 1--5. Ulrich Krengel and Louis Sucheston. 1978. On semiamarts, amarts, and processes with finite value.Advances in Prob 4,197--266 (1978), 1--5."},{"key":"e_1_3_2_1_40_1","volume-title":"IPCO (Lecture Notesin Computer Science)","author":"Lee Euiwoong","unstructured":"Euiwoong Lee and Sahil Singla . 2017. Maximum Matching in the Online Batch-Arrival Model . In IPCO (Lecture Notesin Computer Science) , Vol. 10328 . Springer , 355--367. Euiwoong Lee and Sahil Singla. 2017. Maximum Matching in the Online Batch-Arrival Model. In IPCO (Lecture Notesin Computer Science), Vol. 10328. Springer, 355--367."},{"key":"e_1_3_2_1_41_1","volume-title":"ESA (LIPIcs)","volume":"112","author":"Lee Euiwoong","year":"2018","unstructured":"Euiwoong Lee and Sahil Singla . 2018 . Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities . In ESA (LIPIcs) , Vol. 112 . Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 57:1--57:14. Euiwoong Lee and Sahil Singla. 2018. Optimal Online Contention Resolution Schemes via Ex-Ante Prophet Inequalities. In ESA (LIPIcs), Vol. 112. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 57:1--57:14."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3144722.3144725"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897540"},{"key":"e_1_3_2_1_46_1","unstructured":"Aviad Rubinstein Jack Z Wang and S Matthew Weinberg. 2019. Optimal Single-Choice Prophet Inequalities from Samples. arXiv preprint arXiv:1911.07945(2019).  Aviad Rubinstein Jack Z Wang and S Matthew Weinberg. 2019. Optimal Single-Choice Prophet Inequalities from Samples. arXiv preprint arXiv:1911.07945(2019)."},{"key":"e_1_3_2_1_47_1","volume-title":"1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability 12, 4","author":"Samuel-Cahn Ester","year":"1984","unstructured":"Ester Samuel-Cahn 1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability 12, 4 ( 1984 ), 1213--1216. Ester Samuel-Cahn et al.1984. Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability 12, 4 (1984), 1213--1216."},{"key":"e_1_3_2_1_48_1","volume-title":"ICALP (1) (Lecture Notes in Computer Science)","author":"Wang Yajun","unstructured":"Yajun Wang and Sam Chiu-wai Wong . 2015. Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm . In ICALP (1) (Lecture Notes in Computer Science) , Vol. 9134 . Springer , 1070--1081. Yajun Wang and Sam Chiu-wai Wong. 2015. Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm. In ICALP (1) (Lecture Notes in Computer Science), Vol. 9134. Springer, 1070--1081."}],"event":{"name":"EC '20: The 21st ACM Conference on Economics and Computation","location":"Virtual Event Hungary","acronym":"EC '20","sponsor":["SIGecom Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 21st ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3391403.3399513","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3391403.3399513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:40Z","timestamp":1750200100000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3391403.3399513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,13]]},"references-count":48,"alternative-id":["10.1145\/3391403.3399513","10.1145\/3391403"],"URL":"https:\/\/doi.org\/10.1145\/3391403.3399513","relation":{},"subject":[],"published":{"date-parts":[[2020,7,13]]},"assertion":[{"value":"2020-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}