Search Results

We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski, Böhm, Byrka, Chrobak, Dürr, Folwarczný, Jeż, Sgall, Thang, and Veselý (ESA 2016, OR 2020). In this problem, requests arrive over time at the vertices of a given vertex-weighted tree, and each request has a deadline that it must be served by. The cost of serving a request equals the cost of a path from the root to the vertex where the request resides. Instead of serving each request individually, requests can be aggregated and served by transmitting a subtree from the root that spans the vertices on which the requests reside, to potentially be more cost-effective. The aggregated cost is the weight of the transmission subtree. The goal of MLAP-D is to find an aggregation solution that minimizes the total cost while serving all requests. MLAP-D generalizes some well-studied problems including the TCP acknowledgment problem and the joint replenishment problem, and arises in natural scenarios such as multi-casting, sensor networks, and supply chain management. We present improved and parameterized algorithms for MLAP-D. Our result is twofold. First, we present an e(D+1)-competitive algorithm where D is the depth of the tree. Second, we present an e(4H+2)-competitive algorithm where H is the caterpillar dimension of the tree. Here, H ≤ D and H ≤ log₂ |V| where |V| is the number of vertices in the given tree. The caterpillar dimension remains constant for rich but simple classes of trees, such as line graphs (H = 1), caterpillar graphs (H = 2), and lobster graphs (H = 3). To the best of our knowledge, this is the first online algorithm parameterized on a measure better than depth. The state-of-the-art online algorithms are 6(D+1)-competitive by Buchbinder, Feldman, Naor, and Talmon (SODA 2017) and O(log |V|)-competitive by Azar and Touitou (FOCS 2020). Our framework outperforms the state-of-the-art ratios when H = o(min{D,log₂ |V|}). Our memory-based algorithms extend transmission subtrees with a cost comparable to transmission subtrees used to serve previous requests. Our simple framework directly applies to trees with any structure and differs from the previous frameworks that reduce the problem to trees with specific structures.