{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:58:52Z","timestamp":1773482332528,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T00:00:00Z","timestamp":1568851200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Det Frie Forskningsr\u00e5d","award":["DFF-0602-02499B"],"award-info":[{"award-number":["DFF-0602-02499B"]}]},{"DOI":"10.13039\/100008398","name":"Villum Fonden","doi-asserted-by":"publisher","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/100008398","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>\n            In the online bipartite matching problem with replacements, all the vertices on one side of the bipartition are given, and the vertices on the other side arrive one-by-one with all their incident edges. The goal is to maintain a maximum matching while minimizing the number of changes (replacements) to the matching. We show that the greedy algorithm that always takes the shortest augmenting path from the newly inserted vertex (denoted the SAP protocol) uses at most amortized\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) replacements per insertion, where\n            <jats:italic>n<\/jats:italic>\n            is the total number of vertices inserted. This is the first analysis to achieve a polylogarithmic number of replacements for\n            <jats:italic>any<\/jats:italic>\n            replacement strategy, almost matching the \u03a9 (log\n            <jats:italic>n<\/jats:italic>\n            ) lower bound. The previous best strategy known achieved amortized\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) replacements [Bosek, Leniowski, Sankowski, Zych, FOCS 2014]. For the SAP protocol in particular, nothing better than the trivial\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) bound was known except in special cases. Our analysis immediately implies the same upper bound of\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) reassignments for the capacitated assignment problem, where each vertex on the static side of the bipartition is initialized with the capacity to serve a number of vertices.\n          <\/jats:p>\n          <jats:p>\n            We also analyze the problem of minimizing the maximum server load. We show that if the final graph has maximum server load\n            <jats:italic>L<\/jats:italic>\n            , then the SAP protocol makes amortized\n            <jats:italic>O<\/jats:italic>\n            (min {\n            <jats:italic>L<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            , \u221a\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            }) reassignments. We also show that this is close to tight, because \u03a9 (min {\n            <jats:italic>L<\/jats:italic>\n            , \u221a\n            <jats:italic>n<\/jats:italic>\n            }) reassignments can be necessary.\n          <\/jats:p>","DOI":"10.1145\/3344999","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T15:32:43Z","timestamp":1568907163000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Online Bipartite Matching with Amortized\n            <i>O<\/i>\n            (log\n            <sup>2<\/sup>\n            <i>n<\/i>\n            ) Replacements"],"prefix":"10.1145","volume":"66","author":[{"given":"Aaron","family":"Bernstein","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacob","family":"Holm","sequence":"additional","affiliation":[{"name":"BARC, University of Copenhagen, Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5853-7909","authenticated-orcid":false,"given":"Eva","family":"Rotenberg","sequence":"additional","affiliation":[{"name":"Technical University of Denmark, Lyngby, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"M. Andrews M. X. Goemans and L. Zhang. 1999. Improved bounds for on-line load balancing. Algorithmica 23 4 (01 Apr. 1999) 278--301. DOI:https:\/\/doi.org\/10.1007\/PL00009263  M. Andrews M. X. Goemans and L. Zhang. 1999. Improved bounds for on-line load balancing. Algorithmica 23 4 (01 Apr. 1999) 278--301. DOI:https:\/\/doi.org\/10.1007\/PL00009263","DOI":"10.1007\/PL00009263"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 8th Conference on Innovations in Theoretical Computer Science (ITCS\u201917)","author":"Bernstein A."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897521"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.104"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 55th IEEE Symposium on Foundations of Computer Science (FOCS\u201914)","author":"Bosek B.","year":"2014"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 13th International Workshop on Approximation and Online Algorithms (WAOA\u201915)","author":"Bosek B."},{"key":"e_1_2_1_7_1","unstructured":"B. Bosek D. Leniowski A. Zych and P. Sankowski. 2017. The shortest augmenting paths for online matchings on trees. Retrieved from http:\/\/arxiv.org\/abs\/1704.02093  B. Bosek D. Leniowski A. Zych and P. Sankowski. 2017. The shortest augmenting paths for online matchings on trees. Retrieved from http:\/\/arxiv.org\/abs\/1704.02093"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 31st IEEE International Conference on Computer Communications (INFOCOM\u201909)","author":"Chaudhuri K.","year":"2009"},{"key":"e_1_2_1_9_1","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in a network with power estimation","volume":"11","author":"Dinic E. A.","year":"1970","journal-title":"Soviet Math Doklady"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","volume-title":"Robust Algorithms for Preemptive Scheduling","author":"Epstein Leah","DOI":"10.1007\/978-3-642-23719-5_48"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"E. F. Grove M.-Y. Kao P. Krishnan and J. S. Vitter. 1995. Online perfect matching and mobile computing. In Algorithms and Data Structures S. G. Akl F. Dehne J.-R. Sack and N. Santoro (Eds.). Springer Berlin 194--205.  E. F. Grove M.-Y. Kao P. Krishnan and J. S. Vitter. 1995. Online perfect matching and mobile computing. In Algorithms and Data Structures S. G. Akl F. Dehne J.-R. Sack and N. Santoro (Eds.). Springer Berlin 194--205.","DOI":"10.1007\/3-540-60220-8_62"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488674"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201914)","author":"Gupta A."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055493"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.34"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-10.37.26"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627938"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 22nd ACM Symposium on Theory of Computing (STOC\u201990)","author":"Karp R. M."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 47th ACM Symposium on Theory of Computing (STOC\u201915)","author":"\u0141a\u0327cki Jakub","year":"2015"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.35"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/130917703"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"S. Phillips and J. Westbrook. 1998. On-line load balancing and network flow. Algorithmica 21 3 (01 July 1998) 245--261. DOI:https:\/\/doi.org\/10.1007\/PL00009214  S. Phillips and J. Westbrook. 1998. On-line load balancing and network flow. Algorithmica 21 3 (01 July 1998) 245--261. DOI:https:\/\/doi.org\/10.1007\/PL00009214","DOI":"10.1007\/PL00009214"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0381"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15775-2_4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118733.3118816"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1074"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344999","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344999","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:28Z","timestamp":1750204468000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344999"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,19]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3344999"],"URL":"https:\/\/doi.org\/10.1145\/3344999","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,19]]},"assertion":[{"value":"2018-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}