{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T01:38:52Z","timestamp":1769045932167,"version":"3.49.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T00:00:00Z","timestamp":1593993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002848","name":"Comisi\u00f3n Nacional de Investigaci\u00f3n Cient\u00edfica y Tecnol\u00f3gica","doi-asserted-by":"crossref","award":["FONDECYT 1181527, 1181180, PCI PII 20150140, PIA AFB170001"],"award-info":[{"award-number":["FONDECYT 1181527, 1181180, PCI PII 20150140, PIA AFB170001"]}],"id":[{"id":"10.13039\/501100002848","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"crossref","award":["Excellence Grant 2000020B_182865\/1"],"award-info":[{"award-number":["Excellence Grant 2000020B_182865\/1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,10,31]]},"abstract":"<jats:p>\n            Online models that allow recourse can be highly effective in situations where classical online models are too pessimistic. One such problem is the online machine covering problem on identical machines. In this setting, jobs arrive one by one and must be assigned to machines with the objective of maximizing the minimum machine load. When a job arrives, we are allowed to reassign some jobs as long as their total size is (at most) proportional to the processing time of the arriving job. The proportionality constant is called the\n            <jats:italic>migration factor<\/jats:italic>\n            of the algorithm.\n          <\/jats:p>\n          <jats:p>\n            Using a rounding procedure with useful structural properties for online packing and covering problems, we design first a simple (1.7 + \u03b5)-competitive algorithm using a migration factor of O(1\/\u03b5), which maintains at every arrival a locally optimal solution with respect to the Jump neighborhood. After that, we present as our main contribution a more involved (4\/3+\u03b5)-competitive algorithm using a migration factor of\n            <jats:italic>\u014c<\/jats:italic>\n            (1\/\u03b5\n            <jats:sup>3<\/jats:sup>\n            ). At every arrival, we run an adaptation of the\n            <jats:italic>Largest Processing Time first<\/jats:italic>\n            (LPT) algorithm. Since the new job can cause a complete change of the assignment of smaller jobs in both cases, a low migration factor is achieved by carefully exploiting the highly symmetric structure obtained by the rounding procedure.\n          <\/jats:p>","DOI":"10.1145\/3397535","type":"journal-article","created":{"date-parts":[[2020,7,6]],"date-time":"2020-07-06T21:17:26Z","timestamp":1594070246000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Symmetry Exploitation for Online Machine Covering with Bounded Migration"],"prefix":"10.1145","volume":"16","author":[{"given":"Waldo","family":"G\u00e1lvez","sequence":"first","affiliation":[{"name":"Department of Informatics, Technical University of Munich, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 A.","family":"Soto","sequence":"additional","affiliation":[{"name":"DIM 8 CMM, Universidad de Chile and UMI-CNRS 2807, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9","family":"Verschae","sequence":"additional","affiliation":[{"name":"Instituto de Ingenier\u00eda Matem\u00e1tica y Computacional, Facultad de Matem\u00e1ticas y Escuela de Ingenier\u00eda, Pontificia Universidad Cat\u00f3lica de Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,7,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1425(199808)1:2<67::AID-JOS6>3.0.CO;2-Y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"S. Berndt K. Jansen and K. Klein. 2018. Fully dynamic bin packing revisited. Math. Program. (2018).  S. Berndt K. Jansen and K. Klein. 2018. Fully dynamic bin packing revisited. Math. Program. (2018).","DOI":"10.1007\/s10107-018-1325-x"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.02.033"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90004-M"},{"key":"e_1_2_1_5_1","first-page":"190","article-title":"Scheduling to maximize the minimum processor finish time in a multiprocessor system","volume":"3","author":"Deuermeyer B.","year":"1982","unstructured":"B. Deuermeyer , D. Friesen , and M. Langston . 1982 . Scheduling to maximize the minimum processor finish time in a multiprocessor system . SIJADM 3 (1982), 190 -- 196 . B. Deuermeyer, D. Friesen, and M. Langston. 1982. Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIJADM 3 (1982), 190--196.","journal-title":"SIJADM"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0200-y"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9718-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOCO.0000031420.05971.29"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/140955276"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217033"},{"key":"e_1_2_1_11_1","volume-title":"ICALP","author":"Jansen K.","year":"2013","unstructured":"K. Jansen and K. Klein . 2013. A robust AFPTAS for online bin packing with polynomial migration . In ICALP 2013 . 589--600. K. Jansen and K. Klein. 2013. A robust AFPTAS for online bin packing with polynomial migration. In ICALP 2013. 589--600."},{"key":"e_1_2_1_12_1","volume-title":"ICALP","author":"Jansen K.","year":"2016","unstructured":"K. Jansen , K. Klein , and J. Verschae . 2016. Closing the gap for makespan scheduling via sparsification techniques . In ICALP 2016 . 1--13. K. Jansen, K. Klein, and J. Verschae. 2016. Closing the gap for makespan scheduling via sparsification techniques. In ICALP 2016. 1--13."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746615"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/130917703"},{"key":"e_1_2_1_15_1","first-page":"108","article-title":"Local search performance guarantees for restricted related parallel machine scheduling","volume":"2010","author":"Recalde D.","year":"2010","unstructured":"D. Recalde , C. Rutten , P. Schuurman , and T. Vredeveld . 2010 . Local search performance guarantees for restricted related parallel machine scheduling . LATIN 2010 (2010), 108 -- 119 . D. Recalde, C. Rutten, P. Schuurman, and T. Vredeveld. 2010. Local search performance guarantees for restricted related parallel machine scheduling. LATIN 2010 (2010), 108--119.","journal-title":"LATIN"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0381"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1050.0152"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2015.0765"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"B. V\u00f6cking. 2007. Selfish load balancing. In Algorithmic Game Theory. 517--542.  B. V\u00f6cking. 2007. Selfish load balancing. In Algorithmic Game Theory. 517--542.","DOI":"10.1017\/CBO9780511800481.022"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(96)00055-7"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397535","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:34Z","timestamp":1750193254000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397535"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,6]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,10,31]]}},"alternative-id":["10.1145\/3397535"],"URL":"https:\/\/doi.org\/10.1145\/3397535","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,6]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}