Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.23211 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917111689904128 |
|---|---|
| author | Turoczy, Alexander Lin, Young-San |
| author_facet | Turoczy, Alexander Lin, Young-San |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_23211 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach Turoczy, Alexander Lin, Young-San Data Structures and Algorithms 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. |
| title | Improved and Parameterized Algorithms for Online Multi-level Aggregation: A Memory-based Approach |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.23211 |