{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T08:57:13Z","timestamp":1778576233509,"version":"3.51.4"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T00:00:00Z","timestamp":1560729600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>We introduce a weighted version of the ranking algorithm by Karp et\u00a0al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1\/e barrier even in the vertex-weighted case. We build on the randomized primal-dual framework by Devanur et\u00a0al. (SODA 2013) and design a two dimensional gain sharing function, which depends not only on the rank of the offline vertex, but also on the arrival time of the online vertex. To our knowledge, this is the first competitive ratio strictly larger than 1-1\/e for an online bipartite matching problem achieved under the randomized primal-dual framework. Our algorithm has a natural interpretation that offline vertices offer a larger portion of their weights to the online vertices as time increases, and each online vertex matches the neighbor with the highest offer at its arrival.<\/jats:p>","DOI":"10.1145\/3326169","type":"journal-article","created":{"date-parts":[[2019,6,18]],"date-time":"2019-06-18T12:14:26Z","timestamp":1560860066000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":41,"title":["Online Vertex-Weighted Bipartite Matching"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9046-5236","authenticated-orcid":false,"given":"Zhiyi","family":"Huang","sequence":"first","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhihao Gavin","family":"Tang","sequence":"additional","affiliation":[{"name":"ITCS, Shanghai University of Finance and Economics, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaowei","family":"Wu","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of Vienna, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuhao","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, The University of Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"ESA (LIPIcs)","volume":"57","author":"Abolhassani Melika","year":"2016","unstructured":"Melika Abolhassani , T.-H. Hubert Chan , Fei Chen , Hossein Esfandiari , MohammadTaghi Hajiaghayi , Hamid Mahini , and Xiaowei Wu . 2016 . Beating ratio 0.5 for weighted oblivious matching problems . In ESA (LIPIcs) , Vol. 57 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 3:1--3:18. Melika Abolhassani, T.-H. Hubert Chan, Fei Chen, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Hamid Mahini, and Xiaowei Wu. 2016. Beating ratio 0.5 for weighted oblivious matching problems. In ESA (LIPIcs), Vol. 57. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 3:1--3:18."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Gagan Aggarwal Gagan Goel Chinmay Karande and Aranyak Mehta. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In SODA. 1253--1264.  Gagan Aggarwal Gagan Goel Chinmay Karande and Aranyak Mehta. 2011. Online vertex-weighted bipartite matching and single-bid budgeted allocations. In SODA. 1253--1264.","DOI":"10.1137\/1.9781611973082.95"},{"key":"e_1_2_1_3_1","first-page":"1","article-title":"Randomized greedy matching","volume":"6","author":"Aronson Jonathan","year":"1995","unstructured":"Jonathan Aronson , Martin Dyer , Alan Frieze , and Stephen Suen . 1995 . Randomized greedy matching . II. Random Struct. Algorithms 6 , 1 (Jan. 1995), 55--73. Jonathan Aronson, Martin Dyer, Alan Frieze, and Stephen Suen. 1995. Randomized greedy matching. II. Random Struct. Algorithms 6, 1 (Jan. 1995), 55--73.","journal-title":"II. Random Struct. Algorithms"},{"key":"e_1_2_1_4_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--181. Bahman Bahmani and Michael Kapralov. 2010. Improved bounds for online stochastic matching. In ESA (1) (Lecture Notes in Computer Science), Vol. 6346. Springer, 170--181."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"e_1_2_1_6_1","volume-title":"ESA (LIPIcs)","volume":"57","author":"Brubach Brian","year":"2016","unstructured":"Brian Brubach , Karthik Abinav Sankararaman , Aravind Srinivasan , and Pan Xu . 2016 . New algorithms, better bounds, and a novel model for online stochastic matching . In ESA (LIPIcs) , Vol. 57 . Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 24:1--24:16. Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, and Pan Xu. 2016. New algorithms, better bounds, and a novel model for online stochastic matching. In ESA (LIPIcs), Vol. 57. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, 24:1--24:16."},{"key":"e_1_2_1_7_1","volume-title":"ESA (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 . In ESA (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. In ESA (Lecture Notes in Computer Science), Vol. 4698. Springer, 253--264."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0604"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3168008"},{"key":"e_1_2_1_10_1","unstructured":"T.-H. Hubert Chan Fei Chen Xiaowei Wu and Zhichao Zhao. 2014. Ranking on arbitrary graphs: Rematch via continuous LP with monotone and boundary condition constraints. In SODA. 1112--1122.   T.-H. Hubert Chan Fei Chen Xiaowei Wu and Zhichao Zhao. 2014. Ranking on arbitrary graphs: Rematch via continuous LP with monotone and boundary condition constraints. In SODA. 1112--1122."},{"key":"e_1_2_1_11_1","volume-title":"Randomized online matching in regular graphs","author":"Cohen Ilan Reuven","unstructured":"Ilan Reuven Cohen and David Wajc . 2018. Randomized online matching in regular graphs . In SODA. SIAM , 960--979. Ilan Reuven Cohen and David Wajc. 2018. Randomized online matching in regular graphs. In SODA. SIAM, 960--979."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213992"},{"key":"e_1_2_1_13_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_2_1_14_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--126.  Jon Feldman Aranyak Mehta Vahab S. Mirrokni and S. Muthukrishnan. 2009. Online stochastic matching: Beating 1-1\/e. In FOCS. IEEE Computer Society 117--126.","DOI":"10.1109\/FOCS.2009.72"},{"key":"e_1_2_1_15_1","unstructured":"Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords. In SODA. 982--991.   Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to Adwords. In SODA. 982--991."},{"key":"e_1_2_1_16_1","volume-title":"WINE (Lecture Notes in Computer Science)","author":"Haeupler Bernhard","unstructured":"Bernhard Haeupler , Vahab S. Mirrokni , and Morteza Zadimoghaddam . 2011. Online stochastic weighted matching: Improved approximation algorithms . In WINE (Lecture Notes in Computer Science) , Vol. 7090 . Springer , 170--181. Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2011. Online stochastic weighted matching: Improved approximation algorithms. In WINE (Lecture Notes in Computer Science), Vol. 7090. Springer, 170--181."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188858"},{"key":"e_1_2_1_18_1","volume-title":"ICALP (LIPIcs)","volume":"107","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\u2014Leibniz-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\u2014Leibniz-Zentrum fuer Informatik, 79:1--79:14."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_2_1_22_1","volume-title":"ESA (Lecture Notes in Computer Science)","author":"Kesselheim Thomas","unstructured":"Thomas Kesselheim , Klaus Radke , Andreas T\u00f6nnis , and Berthold V\u00f6cking . 2013. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions . In ESA (Lecture Notes in Computer Science) , Vol. 8125 . Springer , 589--600. Thomas Kesselheim, Klaus Radke, Andreas T\u00f6nnis, and Berthold V\u00f6cking. 2013. An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. In ESA (Lecture Notes in Computer Science), Vol. 8125. Springer, 589--600."},{"key":"e_1_2_1_23_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. 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.","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_26_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."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326169","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3326169","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:08Z","timestamp":1750204388000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3326169"}},"subtitle":["Beating 1-1\/\n            <i>e<\/i>\n            with Random Arrivals"],"short-title":[],"issued":{"date-parts":[[2019,6,17]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3326169"],"URL":"https:\/\/doi.org\/10.1145\/3326169","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,6,17]]},"assertion":[{"value":"2018-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}