{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:17:21Z","timestamp":1751516241343,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,7,7]]},"DOI":"10.1145\/3736252.3742631","type":"proceedings-article","created":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:49:32Z","timestamp":1751482172000},"page":"820-835","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0910-9267","authenticated-orcid":false,"given":"Bo","family":"Peng","sequence":"first","affiliation":[{"name":"Shanghai University of Finance and Economics, Shanghai, China"}]},{"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"}]}],"member":"320","published-online":{"date-parts":[[2025,7,2]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations","author":"Aggarwal Gagan","unstructured":"Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. 2011. Online Vertex-Weighted Bipartite Matching and Single-bid Budgeted Allocations. In SODA. SIAM, 1253\u20131264."},{"key":"e_1_3_2_2_2_1","volume-title":"ESA (1) (Lecture Notes in Computer Science","author":"Bahmani Bahman","unstructured":"Bahman Bahmani and Michael Kapralov. 2010. Improved Bounds for Online Stochastic Matching. In ESA (1) (Lecture Notes in Computer Science, Vol. 6346). Springer, 170\u2013181."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"e_1_3_2_2_4_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_2_5_1","doi-asserted-by":"crossref","unstructured":"Mark Braverman Mahsa Derakhshan and Antonio Molina Lovett. 2022. Max-Weight Online Stochastic Matching: Improved Approximations Against the Online Benchmark. In EC. ACM 967\u2013985.","DOI":"10.1145\/3490486.3538315"},{"key":"e_1_3_2_2_6_1","first-page":"2737","article-title":"Online Stochastic Matching","volume":"82","author":"Brubach Brian","year":"2020","unstructured":"Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2020. Online Stochastic Matching: New Algorithms and Bounds. Algorithmica 82, 10 (2020), 2737\u20132783.","journal-title":"New Algorithms and Bounds. Algorithmica"},{"key":"e_1_3_2_2_7_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. 2018a. Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity. ACM Trans. Algorithms 14, 2 (2018), 12:1\u201312:25.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/140984051"},{"key":"e_1_3_2_2_9_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\u2013107."},{"key":"e_1_3_2_2_10_1","volume-title":"An Economics-Based Analysis of RANKING for Online Bipartite Matching","author":"Eden Alon","unstructured":"Alon Eden, Michal Feldman, Amos Fiat, and Kineret Segal. 2021. An Economics-Based Analysis of RANKING for Online Bipartite Matching. In SOSA. SIAM, 107\u2013110."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3556971"},{"key":"e_1_3_2_2_12_1","volume-title":"Tighter bounds for online bipartite matching. CoRR abs\/1812.11774","author":"Feige Uriel","year":"2018","unstructured":"Uriel Feige. 2018. Tighter bounds for online bipartite matching. CoRR abs\/1812.11774 (2018)."},{"key":"e_1_3_2_2_13_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_2_14_1","volume-title":"to appear. Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching","author":"Feng Yilong","year":"2023","unstructured":"Yilong Feng, Guoliang Qiu, Xiaowei Wu, and Shengwei Zhou. 2023, to appear. Improved Competitive Ratio for Edge-Weighted Online Stochastic Matching. (2023, to appear)."},{"key":"e_1_3_2_2_15_1","unstructured":"Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords. In SODA. 982\u2013991."},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25510-6_15"},{"key":"e_1_3_2_2_17_1","volume-title":"Online Bipartite Matching via Smoothness. CoRR abs\/2203.13140","author":"Hartline Jason D.","year":"2022","unstructured":"Jason D. Hartline. 2022. Online Bipartite Matching via Smoothness. CoRR abs\/2203.13140 (2022)."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"crossref","unstructured":"Zhiyi Huang Hanrui Jiang Aocheng Shen Junkai Song Zhiang Wu and Qiankun Zhang. 2023 to appear. Online Matching with Stochastic Rewards: Advanced Analyses Using Configuration Linear Programs. In WINE.","DOI":"10.1007\/978-3-031-48974-7_22"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3390890"},{"key":"e_1_3_2_2_20_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. 2019a. Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model. In SODA. SIAM, 2875\u20132886."},{"key":"e_1_3_2_2_21_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_2_22_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_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326169"},{"key":"e_1_3_2_2_24_1","volume-title":"Xiaowei Wu, and Yuhao Zhang.","author":"Huang Zhiyi","year":"2020","unstructured":"Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. 2020b. Fully Online Matching II: Beating Ranking and Water-filling. In FOCS. IEEE, 1380\u20131391."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"crossref","unstructured":"Zhiyi Huang and Qiankun Zhang. 2020. Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue. In STOC. ACM 1153\u20131164.","DOI":"10.1145\/3357713.3384294"},{"key":"e_1_3_2_2_26_1","volume-title":"AdWords in a Panorama","author":"Huang Zhiyi","unstructured":"Zhiyi Huang, Qiankun Zhang, and Yuhao Zhang. 2020c. AdWords in a Panorama. In FOCS. IEEE, 1416\u20131426."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_3_2_2_28_1","volume-title":"Williamson","author":"Jin Billy","year":"2021","unstructured":"Billy Jin and David P. Williamson. 2021. Improved Analysis of RANKING for Online Vertex-Weighted Bipartite Matching in the Random Order Model. In WINE (Lecture Notes in Computer Science, Vol. 13112). Springer, 207\u2013225."},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Chinmay Karande Aranyak Mehta and Pushkar Tripathi. 2011. Online bipartite matching with unknown distributions. In STOC. ACM 587\u2013596.","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_3_2_2_30_1","volume-title":"Vazirani","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. ACM, 352\u2013358."},{"key":"e_1_3_2_2_31_1","volume-title":"Streaming Submodular Matching Meets the Primal-Dual Method","author":"Levin Roie","year":"1914","unstructured":"Roie Levin and David Wajc. 2021. Streaming Submodular Matching Meets the Primal-Dual Method. In SODA. SIAM, 1914\u20131933."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Mohammad Mahdian and Qiqi Yan. 2011. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. In STOC. ACM 597\u2013606.","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_3_2_2_35_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_2_36_1","doi-asserted-by":"crossref","unstructured":"Christos H. Papadimitriou Tristan Pollner Amin Saberi and David Wajc. 2021. Online Stochastic Max-Weight Bipartite Matching: Beyond Prophet Inequalities. In EC. ACM 763\u2013764.","DOI":"10.1145\/3465456.3467613"},{"key":"e_1_3_2_2_37_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_2_38_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_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3614318"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.165"}],"event":{"name":"EC '25: 26th ACM Conference on Economics and Computation","location":"Stanford University Stanford CA USA","acronym":"EC '25","sponsor":["SIGecom ACM Special Interest Group on Economics and Computation"]},"container-title":["Proceedings of the 26th ACM Conference on Economics and Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3736252.3742631","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:50:47Z","timestamp":1751482247000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3736252.3742631"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,2]]},"references-count":40,"alternative-id":["10.1145\/3736252.3742631","10.1145\/3736252"],"URL":"https:\/\/doi.org\/10.1145\/3736252.3742631","relation":{},"subject":[],"published":{"date-parts":[[2025,7,2]]},"assertion":[{"value":"2025-07-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}