{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:35:48Z","timestamp":1787510148062,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":27,"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":"Research Grants Council of Hong Kong","award":["HKU17203717E"],"award-info":[{"award-number":["HKU17203717E"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384294","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"1153-1164","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Online primal dual meets online matching with stochastic rewards: configuration LP to the rescue"],"prefix":"10.1145","author":[{"given":"Zhiyi","family":"Huang","sequence":"first","affiliation":[{"name":"University of Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qiankun","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1264","volume-title":"Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Aggarwal Gagan","unstructured":"Gagan Aggarwal , Gagan Goel , Chinmay Karande , and Aranyak Mehta . Online vertex-weighted bipartite matching and single-bid budgeted allocations . In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1253\u2013 1264 . SIAM, 2011. Gagan Aggarwal, Gagan Goel, Chinmay Karande, and Aranyak Mehta. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1253\u20131264. SIAM, 2011."},{"key":"e_1_3_2_1_2_1","volume-title":"Maximum weight online matching with deadlines. arXiv preprint arXiv:1808.03526","author":"Ashlagi Itai","year":"2018","unstructured":"Itai Ashlagi , Maximilien Burq , Chinmoy Dutta , Patrick Jaillet , Amin Saberi , and Chris Sholley . Maximum weight online matching with deadlines. arXiv preprint arXiv:1808.03526 , 2018 . Itai Ashlagi, Maximilien Burq, Chinmoy Dutta, Patrick Jaillet, Amin Saberi, and Chris Sholley. Maximum weight online matching with deadlines. arXiv preprint arXiv:1808.03526, 2018."},{"key":"e_1_3_2_1_3_1","first-page":"181","volume-title":"European Symposium on Algorithms","author":"Bahmani Bahman","unstructured":"Bahman Bahmani and Michael Kapralov . Improved bounds for online stochastic matching . In European Symposium on Algorithms , pages 170\u2013 181 . Springer, 2010. Bahman Bahmani and Michael Kapralov. Improved bounds for online stochastic matching. In European Symposium on Algorithms, pages 170\u2013181. Springer, 2010."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"e_1_3_2_1_5_1","volume-title":"Vertex-weighted online stochastic matching with patience constraints. arXiv preprint arXiv:1907.03963","author":"Brubach Brian","year":"2019","unstructured":"Brian Brubach , Nathaniel Grammel , and Aravind Srinivasan . Vertex-weighted online stochastic matching with patience constraints. arXiv preprint arXiv:1907.03963 , 2019 . Brian Brubach, Nathaniel Grammel, and Aravind Srinivasan. Vertex-weighted online stochastic matching with patience constraints. arXiv preprint arXiv:1907.03963, 2019."},{"key":"e_1_3_2_1_6_1","first-page":"264","volume-title":"European Symposium on Algorithms","author":"Buchbinder Niv","unstructured":"Niv Buchbinder , Kamal Jain , and Joseph Seffi Naor . Online primal-dual algorithms for maximizing ad-auctions revenue . In European Symposium on Algorithms , pages 253\u2013 264 . Springer, 2007. Niv Buchbinder, Kamal Jain, and Joseph Seffi Naor. Online primal-dual algorithms for maximizing ad-auctions revenue. In European Symposium on Algorithms, pages 253\u2013264. Springer, 2007."},{"key":"e_1_3_2_1_7_1","first-page":"78","volume-title":"Proceedings of the 10th ACM Conference on Electronic Commerce","author":"Devanur Nikhil R","unstructured":"Nikhil R Devanur and Thomas P Hayes . The adwords problem: online keyword matching with budgeted bidders under random permutations . In Proceedings of the 10th ACM Conference on Electronic Commerce , pages 71\u2013 78 . ACM, 2009. Nikhil R Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM Conference on Electronic Commerce, pages 71\u201378. ACM, 2009."},{"key":"e_1_3_2_1_8_1","first-page":"144","volume-title":"Proceedings of the 44th Annual ACM Symposium on Theory of Computing","author":"Devanur Nikhil R","unstructured":"Nikhil R Devanur and Kamal Jain . Online matching with concave returns . In Proceedings of the 44th Annual ACM Symposium on Theory of Computing , pages 137\u2013 144 . ACM, 2012. Nikhil R Devanur and Kamal Jain. Online matching with concave returns. In Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pages 137\u2013144. ACM, 2012."},{"key":"e_1_3_2_1_9_1","first-page":"107","volume-title":"Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Devanur Nikhil R","unstructured":"Nikhil R Devanur , Kamal Jain , and Robert D Kleinberg . Randomized primal-dual analysis of ranking for online bipartite matching . In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 101\u2013 107 . SIAM, 2013. Nikhil R Devanur, Kamal Jain, and Robert D Kleinberg. Randomized primal-dual analysis of ranking for online bipartite matching. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 101\u2013107. SIAM, 2013."},{"key":"e_1_3_2_1_10_1","first-page":"126","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science","author":"Feldman Jon","unstructured":"Jon Feldman , Aranyak Mehta , Vahab Mirrokni , and S Muthukrishnan . Online stochastic matching: Beating 1-1\/e . In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science , pages 117\u2013 126 . IEEE, 2009. Jon Feldman, Aranyak Mehta, Vahab Mirrokni, and S Muthukrishnan. Online stochastic matching: Beating 1-1\/e. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 117\u2013126. IEEE, 2009."},{"key":"e_1_3_2_1_11_1","first-page":"991","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Goel Gagan","unstructured":"Gagan Goel and Aranyak Mehta . Online budgeted matching in random input models with applications to adwords . In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 982\u2013 991 . SIAM, 2008. Gagan Goel and Aranyak Mehta. Online budgeted matching in random input models with applications to adwords. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 982\u2013991. SIAM, 2008."},{"key":"e_1_3_2_1_12_1","volume-title":"Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. arXiv preprint arXiv:1905.12778","author":"Goyal Vineet","year":"2019","unstructured":"Vineet Goyal and Rajan Udwani . Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. arXiv preprint arXiv:1905.12778 , 2019 . Vineet Goyal and Rajan Udwani. Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. arXiv preprint arXiv:1905.12778, 2019."},{"key":"e_1_3_2_1_13_1","first-page":"181","volume-title":"International Workshop on Internet and Network Economics","author":"Haeupler Bernhard","unstructured":"Bernhard Haeupler , Vahab S Mirrokni , and Morteza Zadimoghaddam . Online stochastic weighted matching: Improved approximation algorithms . In International Workshop on Internet and Network Economics , pages 170\u2013 181 . Springer, 2011. Bernhard Haeupler, Vahab S Mirrokni, and Morteza Zadimoghaddam. Online stochastic weighted matching: Improved approximation algorithms. In International Workshop on Internet and Network Economics, pages 170\u2013181. Springer, 2011."},{"key":"e_1_3_2_1_14_1","first-page":"29","volume-title":"Proceedings of the 50th Annual ACM Symposium on Theory of Computing","author":"Huang Zhiyi","unstructured":"Zhiyi Huang , Ning Kang , Zhihao Gavin Tang , Xiaowei Wu , Yuhao Zhang , and Xue Zhu . How to match when all vertices arrive online . In Proceedings of the 50th Annual ACM Symposium on Theory of Computing , pages 17\u2013 29 . ACM, 2018. Zhiyi Huang, Ning Kang, Zhihao Gavin Tang, Xiaowei Wu, Yuhao Zhang, and Xue Zhu. How to match when all vertices arrive online. In Proceedings of the 50th Annual ACM Symposium on Theory of Computing, pages 17\u201329. ACM, 2018."},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik","author":"Huang Zhiyi","year":"2018","unstructured":"Zhiyi Huang , Zhihao Gavin Tang , Xiaowei Wu , and Yuhao Zhang . Online vertex-weighted bipartite matching: beating 1-1\/e with random arrivals . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik , 2018 . Zhiyi Huang, Zhihao Gavin Tang, Xiaowei Wu, and Yuhao Zhang. Online vertex-weighted bipartite matching: beating 1-1\/e with random arrivals. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"e_1_3_2_1_16_1","first-page":"2886","volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Huang Zhiyi","unstructured":"Zhiyi Huang , Binghui Peng , Zhihao Gavin Tang , Runzhou Tao , Xiaowei Wu , and Yuhao Zhang . Tight competitive ratios of classic matching algorithms in the fully online model . In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 2875\u2013 2886 . SIAM, 2019. Zhiyi Huang, Binghui Peng, Zhihao Gavin Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. Tight competitive ratios of classic matching algorithms in the fully online model. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2875\u20132886. SIAM, 2019."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_3_2_1_19_1","first-page":"596","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing","author":"Karande Chinmay","unstructured":"Chinmay Karande , Aranyak Mehta , and Pushkar Tripathi . Online bipartite matching with unknown distributions . In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing , pages 587\u2013 596 . ACM, 2011. Chinmay Karande, Aranyak Mehta, and Pushkar Tripathi. Online bipartite matching with unknown distributions. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 587\u2013596. ACM, 2011."},{"key":"e_1_3_2_1_20_1","first-page":"358","volume-title":"Proceedings of the 22nd ACM Symposium on Theory of Computing","author":"Karp Richard M","unstructured":"Richard M Karp , Umesh V Vazirani , and Vijay V Vazirani . An optimal algorithm for on-line bipartite matching . In Proceedings of the 22nd ACM Symposium on Theory of Computing , pages 352\u2013 358 . ACM, 1990. Richard M Karp, Umesh V Vazirani, and Vijay V Vazirani. An optimal algorithm for on-line bipartite matching. In Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 352\u2013358. ACM, 1990."},{"key":"e_1_3_2_1_21_1","first-page":"606","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing","author":"Mahdian Mohammad","unstructured":"Mohammad Mahdian and Qiqi Yan . Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps . In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing , pages 597\u2013 606 . ACM, 2011. Mohammad Mahdian and Qiqi Yan. Online bipartite matching with random arrivals: an approach based on strongly factor-revealing lps. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, pages 597\u2013606. ACM, 2011."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_3_2_1_24_1","first-page":"737","volume-title":"Proceedings of the 53rd IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Mehta Aranyak","unstructured":"Aranyak Mehta and Debmalya Panigrahi . Online matching with stochastic rewards . In Proceedings of the 53rd IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 728\u2013 737 . IEEE, 2012. Aranyak Mehta and Debmalya Panigrahi. Online matching with stochastic rewards. In Proceedings of the 53rd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 728\u2013737. IEEE, 2012."},{"key":"e_1_3_2_1_25_1","first-page":"273","volume-title":"Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science","author":"Mehta Aranyak","unstructured":"Aranyak Mehta , Amin Saberi , Umesh Vazirani , and Vijay Vazirani . Adwords and generalized on-line matching . In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science , pages 264\u2013 273 . IEEE, 2005. Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized on-line matching. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 264\u2013273. IEEE, 2005."},{"key":"e_1_3_2_1_26_1","first-page":"1404","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Mehta Aranyak","unstructured":"Aranyak Mehta , Bo Waggoner , and Morteza Zadimoghaddam . Online stochastic matching with unequal probabilities . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms , pages 1388\u2013 1404 . SIAM, 2015. Aranyak Mehta, Bo Waggoner, and Morteza Zadimoghaddam. Online stochastic matching with unequal probabilities. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1388\u20131404. SIAM, 2015."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007849609234"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"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.3384294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":27,"alternative-id":["10.1145\/3357713.3384294","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384294","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"}}]}}