Online Algorithms for Multilevel Aggregation
- 1 January 2020
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 68 (1) , 214-232
Abstract
Online Algorithms for Hierarchical Aggregation Problems Data and inventory aggregation problems arise in multicasting, sensor networks, communication in organization hierarchies, and in supply chain management. These problems are naturally online, in the sense that aggregation decisions need to be made without information about future requests. We study these problems with a general tree structure of links that can be used for deliveries. This generalizes some well-studied optimization problems: trees of depth one capture the TCP acknowledgment problem, and trees of depth two capture the joint replenishment problem. For trees of depth one and two, constant-competitive online algorithms are known. We solve a major open problem by giving a constant-competitive algorithm for trees of arbitrary (fixed) depth. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines.Keywords
All Related Versions
This publication has 32 references indexed in Scilit:
- Competitive Analysis of Organization Networks or Multicast Acknowledgment: How Much to Wait?Algorithmica, 2011
- Latency-constrained aggregation in sensor networksACM Transactions on Algorithms, 2009
- APPROXIMATING THE JOINT REPLENISHMENT PROBLEM WITH DEADLINESDiscrete Mathematics, Algorithms and Applications, 2009
- The Design of Competitive Online Algorithms via a Primal—Dual ApproachFoundations and Trends® in Theoretical Computer Science, 2009
- Dynamic TCP Acknowledgment: Penalizing Long DelaysSIAM Journal on Discrete Mathematics, 2005
- Dynamic TCP acknowledgment in the LogP modelJournal of Algorithms, 2003
- On-line analysis of the TCP acknowledgment delay problemJournal of the ACM, 2001
- Issues in Supply Chain ManagementIndustrial Marketing Management, 2000
- On-line scheduling1998
- Computational complexity of uncapacitated multi-echelon production planning problemsOperations Research Letters, 1989