{"ID":2835532,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.23211","arxiv_id":"2511.23211","title":"Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach","abstract":"We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski et al. (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. 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 \\le D$ and $H \\le \\log_2 |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_2 |V|\\})$. 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.","short_abstract":"We study the online multi-level aggregation problem with deadlines (MLAP-D) introduced by Bienkowski et al. (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...","url_abs":"https://arxiv.org/abs/2511.23211","url_pdf":"https://arxiv.org/pdf/2511.23211v1","authors":"[\"Alexander Turoczy\",\"Young-San Lin\"]","published":"2025-11-28T14:17:57Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}