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.

Publication
Lecture Notes in Computer Science
Rodrigo A. Carrasco
Rodrigo A. Carrasco
Academic Director Master in Industrial Engineering / Assistant Professor
Kirk Pruhs
Kirk Pruhs
University of Pittsburgh
Cliff Stein
Cliff Stein
Columbia University
José Verschae
José Verschae
Pontificia Universidad Católica de Chile