{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:20:18Z","timestamp":1740136818130,"version":"3.37.3"},"reference-count":37,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research"],"published-print":{"date-parts":[[2020,1]]},"abstract":" Online Algorithms for Hierarchical Aggregation Problems <\/jats:p> Data and inventory aggregation problems arise in multicasting, sensor networks, communication in organization hierarchies, and in supply chain management. These problems are naturally online, in the sense that aggregation decisions need to be made without information about future requests. We study these problems with a general tree structure of links that can be used for deliveries. This generalizes some well-studied optimization problems: trees of depth one capture the TCP acknowledgment problem, and trees of depth two capture the joint replenishment problem. For trees of depth one and two, constant-competitive online algorithms are known. We solve a major open problem by giving a constant-competitive algorithm for trees of arbitrary (fixed) depth. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. <\/jats:p>","DOI":"10.1287\/opre.2019.1847","type":"journal-article","created":{"date-parts":[[2020,1,2]],"date-time":"2020-01-02T16:36:11Z","timestamp":1577982971000},"page":"214-232","source":"Crossref","is-referenced-by-count":2,"title":["Online Algorithms for Multilevel Aggregation"],"prefix":"10.1287","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2453-7772","authenticated-orcid":false,"given":"Marcin","family":"Bienkowski","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, 50-137 Wroc\u0142aw, Poland;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4796-7422","authenticated-orcid":false,"given":"Martin","family":"B\u00f6hm","sequence":"additional","affiliation":[{"name":"CSLog, University of Bremen, 28359 Bremen, Germany;"},{"name":"Computer Science Institute, Charles University, 118 00 Prague, Czech Republic;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3387-0913","authenticated-orcid":false,"given":"Jaroslaw","family":"Byrka","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, 50-137 Wroc\u0142aw, Poland;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8673-2709","authenticated-orcid":false,"given":"Marek","family":"Chrobak","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of California, Riverside, Riverside, California 92521;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8103-5333","authenticated-orcid":false,"given":"Christoph","family":"D\u00fcrr","sequence":"additional","affiliation":[{"name":"Laboratoire d\u2019Informatique de Paris 6, Sorbonne Universit\u00e9, Centre National de la Recherche Scientifique, 75252 Paris, France;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3020-6443","authenticated-orcid":false,"given":"Luk\u00e1\u0161","family":"Folwarczn\u00fd","sequence":"additional","affiliation":[{"name":"Computer Science Institute, Charles University, 118 00 Prague, Czech Republic;"},{"name":"Institute of Mathematics, Czech Academy of Sciences, 110 00 Prague, Czech Republic;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7375-0641","authenticated-orcid":false,"given":"\u0141ukasz","family":"Je\u017c","sequence":"additional","affiliation":[{"name":"Institute of Computer Science, University of Wroc\u0142aw, 50-137 Wroc\u0142aw, Poland;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3658-4848","authenticated-orcid":false,"given":"Ji\u0159\u00ed","family":"Sgall","sequence":"additional","affiliation":[{"name":"Computer Science Institute, Charles University, 118 00 Prague, Czech Republic;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6085-9453","authenticated-orcid":false,"given":"Nguyen Kim","family":"Thang","sequence":"additional","affiliation":[{"name":"Laboratoire Informatique, Bio-informatique et Syst\u00e8mes Complexes, Universit\u00e9 d\u2019Evry Val d\u2019Essonne, 91034 Evry, France;"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-7934","authenticated-orcid":false,"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"Computer Science Institute, Charles University, 118 00 Prague, Czech Republic;"},{"name":"Department of Computer Science, University of Warwick, CV4 7AL Coventry, United Kingdom"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.41.3.549"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104441656"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90001-1"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch11"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055475"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCN.2000.885492"},{"key":"B7","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548477"},{"key":"B8","doi-asserted-by":"publisher","DOI":"10.1145\/1644015.1644028"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.4"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40104-6_12"},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-014-0392-y"},{"key":"B12","first-page":"12:1","volume-title":"Proc. 24th Eur. Sympos. Algorithms","author":"Bienkowski M","year":"2016"},{"volume-title":"Online Computation and Competitive Analysis","year":"1998","author":"Borodin A","key":"B13"},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.1998.665111"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9567-5"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1561\/0400000024"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.80"},{"key":"B18","first-page":"952","volume-title":"Proc. 19th ACM-SIAM Sympos. Discrete Algorithms","author":"Buchbinder N","year":"2008"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.20.1.14"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375843"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00058-0"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1109\/ITCC.2005.219"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1013-x"},{"key":"B24","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45465-9_13"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-50162-3"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-8501(99)00113-3"},{"key":"B27","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_19"},{"key":"B28","first-page":"365","volume-title":"Proc. 16th ACM-SIAM Sympos. Discrete Algorithms","author":"Levi R","year":"2005"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0178"},{"key":"B30","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.1070.0781"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830909000130"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61680-2_82"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335385"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0029570"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332499"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.5.1.89"},{"key":"B38","first-page":"221","volume-title":"Proc. Global Telecomm. Conf.","author":"Yuan W","year":"2003"}],"container-title":["Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/opre.2019.1847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,2]],"date-time":"2023-04-02T21:11:45Z","timestamp":1680469905000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/opre.2019.1847"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["10.1287\/opre.2019.1847"],"URL":"https:\/\/doi.org\/10.1287\/opre.2019.1847","relation":{},"ISSN":["0030-364X","1526-5463"],"issn-type":[{"type":"print","value":"0030-364X"},{"type":"electronic","value":"1526-5463"}],"subject":[],"published":{"date-parts":[[2020,1]]}}}