{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:41:41Z","timestamp":1781077301063,"version":"3.54.1"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,5,18]],"date-time":"2020-05-18T00:00:00Z","timestamp":1589760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Start-up Research Grant of University of Macau","award":["SRG2020-00020-IOTSC"],"award-info":[{"award-number":["SRG2020-00020-IOTSC"]}]},{"name":"Science and Technology Development Fund, Macau SAR","award":["SKL-IOTSC-2018-2020"],"award-info":[{"award-number":["SKL-IOTSC-2018-2020"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61902233"],"award-info":[{"award-number":["61902233"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Hong Kong Research Grants Council","award":["17202019E"],"award-info":[{"award-number":["17202019E"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,6,30]]},"abstract":"<jats:p>We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors\u2019 arrivals. If a vertex remains unmatched until its deadline, then the algorithm must irrevocably either match it to an unmatched neighbor or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, and so on.<\/jats:p>\n          <jats:p>We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step toward solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, then we show a tight competitive ratio \u22480.5671 of Ranking. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 &lt; 1- 1\/e-competitive in our model, even for bipartite graphs.<\/jats:p>","DOI":"10.1145\/3390890","type":"journal-article","created":{"date-parts":[[2020,5,22]],"date-time":"2020-05-22T23:48:14Z","timestamp":1590191294000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Fully Online Matching"],"prefix":"10.1145","volume":"67","author":[{"given":"Zhiyi","family":"Huang","sequence":"first","affiliation":[{"name":"The University of Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ning","family":"Kang","sequence":"additional","affiliation":[{"name":"Huawei Noah\u2019s Ark Lab, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"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, Yangpu District, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1879-6089","authenticated-orcid":false,"given":"Xiaowei","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Macau, Taipa, Macau, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuhao","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xue","family":"Zhu","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,5,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201916)","volume":"57","author":"Abolhassani Melika","year":"2016"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","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","journal-title":"II. Random Struct. Algorithms"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329573"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1360443.1360462"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75520-3_24"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA\u201917)","volume":"87","author":"Buchbinder Niv","year":"2017"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.82"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_28"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201912)","author":"Nikhil"},{"key":"e_1_2_1_11_1","volume-title":"Kleinberg","author":"Devanur Nikhil R.","year":"2013"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","volume":"20","author":"Epstein Leah","year":"2013"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00011"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201908)","author":"Goel Gagan","year":"2008"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","volume":"107","author":"Huang Zhiyi","year":"2018"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993715"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\u201990)","author":"Karp Richard M."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993716"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11538462_15"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284321"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.20"},{"key":"e_1_2_1_22_1","unstructured":"Zhihao Gavin Tang Xiaowei Wu and Yuhao Zhang. 2019. Toward a better understanding of randomized greedy matching. CoRR abs\/1907.05135.  Zhihao Gavin Tang Xiaowei Wu and Yuhao Zhang. 2019. Toward a better understanding of randomized greedy matching. CoRR abs\/1907.05135."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22006-7_32"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_87"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3390890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3390890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:36Z","timestamp":1750199916000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3390890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,18]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,6,30]]}},"alternative-id":["10.1145\/3390890"],"URL":"https:\/\/doi.org\/10.1145\/3390890","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,18]]},"assertion":[{"value":"2019-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}