{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,11]],"date-time":"2026-05-11T10:25:50Z","timestamp":1778495150068,"version":"3.51.4"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T00:00:00Z","timestamp":1668643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["DGE-1650044"],"award-info":[{"award-number":["DGE-1650044"]}]},{"name":"RGC","award":["17203"],"award-info":[{"award-number":["17203"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,12,31]]},"abstract":"<jats:p>Online bipartite matching is one of the most fundamental problems in the online algorithms literature. Karp, Vazirani, and Vazirani (STOC 1990) gave an elegant algorithm for unweighted bipartite matching that achieves an optimal competitive ratio of 1-1\/e . Aggarwal et\u00a0al.\u00a0(SODA 2011) later generalized their algorithm and analysis to the vertex-weighted case. Little is known, however, about the most general edge-weighted problem aside from the trivial 1\/2-competitive greedy algorithm. In this article, we present the first online algorithm that breaks the long-standing 1\/2 barrier and achieves a competitive ratio of at least\u00a00.5086. In light of the hardness result of Kapralov, Post, and Vondr\u00e1k\u00a0(SODA 2013), which restricts beating a\u00a0 1\/2  competitive ratio for the more general monotone submodular welfare maximization problem, our result can be seen as strong evidence that edge-weighted bipartite matching is strictly easier than submodular welfare maximization in an online setting.<\/jats:p>\n          <jats:p>\n            The main ingredient in our online matching algorithm is a novel subroutine called\n            <jats:italic>online correlated selection<\/jats:italic>\n            \u00a0(OCS), which takes a sequence of pairs of vertices as input and selects one vertex from each pair. Instead of using a fresh random bit to choose a vertex from each pair, the OCS negatively correlates decisions across different pairs and provides a quantitative measure on the level of correlation. We believe our OCS technique is of independent interest and will find further applications in other online optimization problems.\n          <\/jats:p>","DOI":"10.1145\/3556971","type":"journal-article","created":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T10:56:30Z","timestamp":1660388190000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Edge-Weighted Online Bipartite Matching"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3142-7133","authenticated-orcid":false,"given":"Matthew","family":"Fahrbach","sequence":"first","affiliation":[{"name":"Google Research, New York, NY, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2963-9556","authenticated-orcid":false,"given":"Zhiyi","family":"Huang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Pokfulam, Hong Kong"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3733-5168","authenticated-orcid":false,"given":"Runzhou","family":"Tao","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, United States"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0717-1120","authenticated-orcid":false,"given":"Morteza","family":"Zadimoghaddam","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY, United States"}]}],"member":"320","published-online":{"date-parts":[[2022,11,17]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133131"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329573"},{"key":"e_1_3_3_4_2","volume-title":"Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science","author":"Blanc Guy","year":"2021","unstructured":"Guy Blanc and Moses Charikar. 2021. Multiway online correlated selection. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 1277\u20131284."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00603-7"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-019-01459-z"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778606"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/1566374.1566384"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2892563"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627824"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993574.1993581"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764536"},{"key":"e_1_3_3_13_2","article-title":"Online weighted matching: Breaking the  \\( \\frac{1}{2} \\)  barrier","author":"Fahrbach Matthew","year":"2019","unstructured":"Matthew Fahrbach and Morteza Zadimoghaddam. 2019. Online weighted matching: Breaking the \\( \\frac{1}{2} \\) barrier. arXiv preprint arXiv:1704.05384v2.","journal-title":"arXiv preprint arXiv:1704.05384v2"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.5555\/1888935.1888957"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1007\/978-3-642-10841-9_34","volume-title":"International Workshop on Internet and Network Economics","author":"Feldman Jon","year":"2009","unstructured":"Jon Feldman, Nitish Korula, Vahab S. Mirrokni, Shanmugavelayutham Muthukrishnan, and Martin P\u00e1l. 2009. Online ad assignment with free disposal. In International Workshop on Internet and Network Economics. Springer, 374\u2013385."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.72"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.176"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00011"},{"key":"e_1_3_3_20_2","volume-title":"Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science","author":"Gao Ruiquan","year":"2021","unstructured":"Ruiquan Gao, Zhongtian He, Zhiyi Huang, Zipei Nie, Bijun Yuan, and Yan Zhong. 2021. Improved online correlated selection. In Proceedings of the 62nd Annual IEEE Symposium on Foundations of Computer Science. IEEE, 1265\u20131276."},{"key":"e_1_3_3_21_2","first-page":"982","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Goel Gagan","year":"2008","unstructured":"Gagan Goel and Aranyak Mehta. 2008. Online budgeted matching in random input models with applications to adwords. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 982\u2013991."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_20"},{"key":"e_1_3_3_23_2","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1007\/978-3-642-25510-6_15","volume-title":"International Workshop on Internet and Network Economics","author":"Haeupler Bernhard","year":"2011","unstructured":"Bernhard Haeupler, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2011. Online stochastic weighted matching: Improved approximation algorithms. In International Workshop on Internet and Network Economics. Springer, 170\u2013181."},{"key":"e_1_3_3_24_2","article-title":"Understanding Zadimoghaddam\u2019s edge-weighted online matching algorithm: Weighted case","author":"Huang Zhiyi","year":"2019","unstructured":"Zhiyi Huang. 2019. Understanding Zadimoghaddam\u2019s edge-weighted online matching algorithm: Weighted case. arXiv preprint arXiv:1910.03287 (2019).","journal-title":"arXiv preprint arXiv:1910.03287"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188858"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.178"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451079"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520046"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/3326169"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00130"},{"key":"e_1_3_3_31_2","article-title":"Understanding Zadimoghaddam\u2019s edge-weighted online matching algorithm: Unweighted case","author":"Huang Zhiyi","year":"2019","unstructured":"Zhiyi Huang and Runzhou Tao. 2019. Understanding Zadimoghaddam\u2019s edge-weighted online matching algorithm: Unweighted case. arXiv preprint arXiv:1910.02569","journal-title":"arXiv preprint arXiv:1910.02569"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00133"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0621"},{"key":"e_1_3_3_34_2","first-page":"207","volume-title":"International Conference on Web and Internet Economics","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 International Conference on Web and Internet Economics. Springer, 207\u2013225."},{"key":"e_1_3_3_35_2","first-page":"286","article-title":"Negative association of random variables with applications","author":"Joag-Dev Kumar","year":"1983","unstructured":"Kumar Joag-Dev and Frank Proschan. 1983. Negative association of random variables with applications. The Annals of Statistics (1983), 286\u2013295.","journal-title":"The Annals of Statistics"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00140-1"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.88"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100262"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45046-4_25"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1051142"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1120.0551"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000057"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.12"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.134"},{"key":"e_1_3_3_48_2","volume-title":"Proceedings of the 32nd International Symposium on Algorithms and Computation","author":"Shin Yongho","year":"2021","unstructured":"Yongho Shin and Hyung-Chan An. 2021. Making three out of two: three-way online correlated selection. In Proceedings of the 32nd International Symposium on Algorithms and Computation. Schloss Dagstuhl, 49:1\u201349:17."},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519994"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556971","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3556971","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3556971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:48:52Z","timestamp":1750286932000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3556971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,17]]},"references-count":48,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12,31]]}},"alternative-id":["10.1145\/3556971"],"URL":"https:\/\/doi.org\/10.1145\/3556971","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,11,17]]},"assertion":[{"value":"2021-02-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-11-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}