{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T12:48:13Z","timestamp":1763642893020,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":22,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Natural Science Foundation of China (NSFC)","award":["61902233"],"award-info":[{"award-number":["61902233"]}]},{"name":"European Community?s Seventh Framework Programme (FP7\/2007-2013)","award":["340506"],"award-info":[{"award-number":["340506"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384265","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1097-1110","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Towards a better understanding of randomized greedy matching"],"prefix":"10.1145","author":[{"given":"Zhihao Gavin","family":"Tang","sequence":"first","affiliation":[{"name":"Shanghai University of Finance and Economics, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaowei","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Macau, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhao","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060107"},{"key":"e_1_3_2_1_2_1","article-title":"Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity","volume":"14","author":"Hubert Chan T.-H.","year":"2018","unstructured":"T.-H. Hubert Chan , Fei Chen , and Xiaowei Wu . 2018 . Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity . ACM Trans. Algorithms 14 , 2 ( 2018 ), 12 : 1-12 : 25. T.-H. Hubert Chan, Fei Chen, and Xiaowei Wu. 2018. Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity. ACM Trans. Algorithms 14, 2 ( 2018 ), 12 : 1-12 : 25.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/140984051"},{"volume-title":"ICALP (1) (Lecture Notes in Computer Science)","author":"Chen Ning","key":"e_1_3_2_1_4_1","unstructured":"Ning Chen , Nicole Immorlica , Anna R. Karlin , Mohammad Mahdian , and Atri Rudra . 2009. Approximating Matches Made in Heaven . In ICALP (1) (Lecture Notes in Computer Science) , Vol. 5555 . Springer , 266-278. Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, and Atri Rudra. 2009. Approximating Matches Made in Heaven. In ICALP (1) (Lecture Notes in Computer Science), Vol. 5555. Springer, 266-278."},{"volume-title":"ICALP (1) (Lecture Notes in Computer Science)","author":"Costello Kevin P.","key":"e_1_3_2_1_5_1","unstructured":"Kevin P. Costello , Prasad Tetali , and Pushkar Tripathi . 2012. Stochastic Matching with Commitment . In ICALP (1) (Lecture Notes in Computer Science) , Vol. 7391 . Springer , 822-833. Kevin P. Costello, Prasad Tetali, and Pushkar Tripathi. 2012. Stochastic Matching with Commitment. In ICALP (1) (Lecture Notes in Computer Science), Vol. 7391. Springer, 822-833."},{"key":"e_1_3_2_1_6_1","volume-title":"Kleinberg","author":"Devanur Nikhil R.","year":"2013","unstructured":"Nikhil R. Devanur , Kamal Jain , and Robert D . Kleinberg . 2013 . Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching. In SODA. SIAM , 101-107. Nikhil R. Devanur, Kamal Jain, and Robert D. Kleinberg. 2013. Randomized Primal-Dual analysis of RANKING for Online BiPartite Matching. In SODA. SIAM, 101-107."},{"key":"e_1_3_2_1_7_1","volume-title":"Frieze","author":"Dyer Martin E.","year":"1991","unstructured":"Martin E. Dyer and Alan M . Frieze . 1991 . Randomized Greedy Matching. Random Struct. Algorithms 2, 1 ( 1991 ), 29-46. Martin E. Dyer and Alan M. Frieze. 1991. Randomized Greedy Matching. Random Struct. Algorithms 2, 1 ( 1991 ), 29-46."},{"volume-title":"Beating Greedy for Stochastic Bipartite Matching","author":"Gamlath Buddhima","key":"e_1_3_2_1_8_1","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_9_1","first-page":"718","article-title":"Matching with Our Eyes Closed","author":"Goel Gagan","year":"2012","unstructured":"Gagan Goel and Pushkar Tripathi . 2012 . Matching with Our Eyes Closed . In FOCS. 718 - 727 . Gagan Goel and Pushkar Tripathi. 2012. Matching with Our Eyes Closed. In FOCS. 718-727.","journal-title":"FOCS."},{"key":"e_1_3_2_1_10_1","volume-title":"Understanding Zadimoghaddam's Edge-weighted Online Matching Algorithm: Weighted Case. CoRR abs\/","author":"Huang Zhiyi","year":"1910","unstructured":"Zhiyi Huang . 2019. Understanding Zadimoghaddam's Edge-weighted Online Matching Algorithm: Weighted Case. CoRR abs\/ 1910 .03287 ( 2019 ). Zhiyi Huang. 2019. Understanding Zadimoghaddam's Edge-weighted Online Matching Algorithm: Weighted Case. CoRR abs\/ 1910.03287 ( 2019 )."},{"key":"e_1_3_2_1_11_1","first-page":"17","article-title":"How to match when all vertices arrive online","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.","journal-title":"STOC. ACM"},{"key":"e_1_3_2_1_12_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_13_1","volume-title":"Xiaowei Wu, and Yuhao Zhang.","author":"Huang Zhiyi","year":"2018","unstructured":"Zhiyi Huang , Zhihao Gavin Tang , Xiaowei Wu, and Yuhao Zhang. 2018 . Online Vertex-Weighted Bipartite Matching: Beating 1-1\/e with Random Arrivals. In ICALP (LIPIcs), Vol. 107 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik , 79 : 1-79 : 14. Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. 2018. Online Vertex-Weighted Bipartite Matching: Beating 1-1\/e with Random Arrivals. In ICALP (LIPIcs), Vol. 107. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 79 : 1-79 : 14."},{"key":"e_1_3_2_1_14_1","first-page":"587","article-title":"Online bipartite matching with unknown distributions","author":"Karande Chinmay","year":"2011","unstructured":"Chinmay Karande , Aranyak Mehta , and Pushkar Tripathi . 2011 . Online bipartite matching with unknown distributions . In STOC. 587 - 596 . Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. 2011. Online bipartite matching with unknown distributions. In STOC. 587-596.","journal-title":"STOC."},{"key":"e_1_3_2_1_15_1","first-page":"352","article-title":"An Optimal Algorithm for On-line Bipartite Matching","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 STOC. 352 - 358 . Richard M. Karp, Umesh V. Vazirani, and Vijay V. Vazirani. 1990. An Optimal Algorithm for On-line Bipartite Matching. In STOC. 352-358.","journal-title":"STOC."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297131"},{"key":"e_1_3_2_1_17_1","first-page":"597","article-title":"Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs","author":"Mahdian Mohammad","year":"2011","unstructured":"Mohammad Mahdian and Qiqi Yan . 2011 . Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs . In STOC. 597 - 606 . Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In STOC. 597-606.","journal-title":"STOC."},{"key":"e_1_3_2_1_18_1","first-page":"708","article-title":"Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis","author":"Poloczek Matthias","year":"2012","unstructured":"Matthias Poloczek and Mario Szegedy . 2012 . Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis . In FOCS. 708 - 717 . Matthias Poloczek and Mario Szegedy. 2012. Randomized Greedy Algorithms for the Maximum Matching Problem with New Analysis. In FOCS. 708-717.","journal-title":"FOCS."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2005.04.004"},{"key":"e_1_3_2_1_20_1","unstructured":"Zhihao Gavin Tang Xiaowei Wu and Yuhao Zhang. 2020. Towards a Better Understanding of Randomized Greedy Matching. ( 2020 ).  Zhihao Gavin Tang Xiaowei Wu and Yuhao Zhang. 2020. Towards a Better Understanding of Randomized Greedy Matching. ( 2020 )."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01874391"},{"key":"e_1_3_2_1_22_1","unstructured":"Morteza Zadimoghaddam. 2017. Online Weighted Matching: Beating the 1\/2 Barrier. CoRR abs\/1704.05384 ( 2017 ).  Morteza Zadimoghaddam. 2017. Online Weighted Matching: Beating the 1\/2 Barrier. CoRR abs\/1704.05384 ( 2017 )."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Chicago IL USA","acronym":"STOC '20"},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384265","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":22,"alternative-id":["10.1145\/3357713.3384265","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384265","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}