@inproceedings{772818f802bd4ea3aacbbcbad69a85a8,
title = "The online set aggregation problem",
abstract = "We introduce the online Set Aggregation Problem, which is a natural generalization of the Multi-Level Aggregation Problem, which in turn generalizes the TCP Acknowledgment Problem and the Joint Replenishment Problem. We give a deterministic online algorithm, and show that its competitive ratio is logarithmic in the number of requests. We also give a matching lower bound on the competitive ratio of any randomized online algorithm.",
keywords = "Competitive analysis, Multilevel aggregation, Online algorithms, Set aggregation",
author = "Carrasco, {Rodrigo A.} and Kirk Pruhs and Cliff Stein and Jos{\'e} Verschae",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 13th International Symposium on Latin American Theoretical Informatics, LATIN 2018 ; Conference date: 16-04-2018 Through 19-04-2018",
year = "2018",
doi = "10.1007/978-3-319-77404-6_19",
language = "English",
isbn = "9783319774039",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "245--259",
editor = "Mosteiro, {Miguel A.} and Bender, {Michael A.} and Martin Farach-Colton",
booktitle = "LATIN 2018",
}