O(depth)-competitive algorithm for online multi-level aggregation

DOI10.1137/1.9781611974782.80zbMATH Open1411.68201arXiv1701.01936OpenAlexW4240846525MaRDI QIDQ4575823FDOQ4575823

Authors: Niv Buchbinder, Moran Feldman, Joseph (Seffi) Naor, Ohad Talmon 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: We consider a multi-level aggregation problem in a weighted rooted tree, studied recently by Bienkowski et al. (2015). In this problem requests arrive over time at the nodes of the tree, and each request specifies a deadline. A request is served by sending it to the root before its deadline at a cost equal to the weight of the path from the node in which it resides to the root. However, requests from different nodes can be aggregated, and served together, so as to save on cost. The cost of serving an aggregated set of requests is equal to the weight of the subtree spanning the nodes in which the requests reside. Thus, the problem is to find a competitive online aggregation algorithm that minimizes the total cost of the aggregated requests. This problem arises naturally in many scenarios, including multicasting, supply-chain management and sensor networks. It is also related to the well studied TCP-acknowledgement problem and the online joint replenishment problem. We present an online $O(D)$-competitive algorithm for the problem, where $D$ is the depth, or number of levels, of the aggregation tree. This result improves upon the $D^2{2}^D$-competitive algorithm obtained recently by Bienkowski et al. (2015).

Full work available at URL: https://arxiv.org/abs/1701.01936

Recommendations

• Online Algorithms for Multilevel Aggregation
• Online algorithms for multi-level aggregation
• New results on multi-level aggregation
• The online set aggregation problem
• Online control message aggregation in chain networks

zbMATH Keywords

online algorithmscompetitive analysisaggregation of requests

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Cited In (9)

• Online control message aggregation in chain networks
• Online algorithms for multi-level aggregation
• Caching with time windows and delays
• New results on multi-level aggregation
• Title not available (Why is that?)
• Tight bounds for delay-sensitive aggregation
• Online Algorithms for Multilevel Aggregation
• The online set aggregation problem
• Improved and deterministic online service with deadlines or delay

This page was built for publication: \(O(\mathrm{depth})\)-competitive algorithm for online multi-level aggregation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575823)