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.
Type
Publication
Lecture Notes in Computer Science
Rodrigo A. Carrasco
Associate Professor & the UC Data Science Initiative Director
Kirk Pruhs
University of Pittsburgh
Cliff Stein
Columbia University
