Document Open Access Logo

Online Algorithms for Multi-Level Aggregation

Authors Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, Pavel Vesely

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.12.pdf
  • Filesize: 0.57 MB
  • 17 pages

Document Identifiers

Author Details

Marcin Bienkowski
Martin Böhm
Jaroslaw Byrka
Marek Chrobak
Christoph Dürr
Lukas Folwarczny
Lukasz Jez
Jiri Sgall
Nguyen Kim Thang
Pavel Vesely

Cite AsGet BibTex

Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukas Folwarczny, Lukasz Jez, Jiri Sgall, Nguyen Kim Thang, and Pavel Vesely. Online Algorithms for Multi-Level Aggregation. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.12

Abstract

In the Multi-Level Aggregation Problem (MLAP), requests arrive at the nodes of an edge-weighted tree T, and have to be served eventually. A service is defined as a subtree X of T that contains its root. This subtree X serves all requests that are pending in the nodes of X, and the cost of this service is equal to the total weight of X. Each request also incurs waiting cost between its arrival and service times. The objective is to minimize the total waiting cost of all requests plus the total cost of all service subtrees. MLAP is a generalization of some well-studied optimization problems; for example, for trees of depth 1, MLAP is equivalent to the TCP Acknowledgment Problem, while for trees of depth 2, it is equivalent to the Joint Replenishment Problem. Aggregation problem for trees of arbitrary depth arise in multicasting, sensor networks, communication in organization hierarchies, and in supply-chain management. The instances of MLAP associated with these applications are naturally online, in the sense that aggregation decisions need to be made without information about future requests. Constant-competitive online algorithms are known for MLAP with one or two levels. However, it has been open whether there exist constant competitive online algorithms for trees of depth more than 2. Addressing this open problem, we give the first constant competitive online algorithm for networks of arbitrary (fixed) number of levels. The competitive ratio is O(D^4*2^D), where D is the depth of T. The algorithm works for arbitrary waiting cost functions, including the variant with deadlines. We include several additional results in the paper. We show that a standard lower-bound technique for MLAP, based on so-called Single-Phase instances, cannot give super-constant lower bounds (as a function of the tree depth). This result is established by giving an online algorithm with optimal competitive ratio 4 for such instances on arbitrary trees. We also study the MLAP variant when the tree is a path, for which we give a lower bound of 4 on the competitive ratio, improving the lower bound known for general MLAP. We complement this with a matching upper bound for the deadline setting.
Keywords
  • algorithmic aspects of networks
  • online algorithms
  • scheduling and resource allocation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Alok Aggarwal and James K. Park. Improved algorithms for economic lot sizing problems. Operations Research, 41:549-571, 1993. Google Scholar
  2. Esther Arkin, Dev Joneja, and Robin Roundy. Computational complexity of uncapacitated multi-echelon production planning problems. Operations Research Letters, 8(2):61-66, 1989. Google Scholar
  3. B. R. Badrinath and Pradeep Sudame. Gathercast: the design and implementation of a programmable aggregation mechanism for the internet. In Proc. 9thInternational Conference on Computer Communications and Networks (ICCCN), pages 206-213, 2000. Google Scholar
  4. Luca Becchetti, Alberto Marchetti-Spaccamela, Andrea Vitaletti, Peter Korteweg, Martin Skutella, and Leen Stougie. Latency-constrained aggregation in sensor networks. ACM Transactions on Algorithms, 6(1):13:1-13:20, 2009. Google Scholar
  5. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Neil B. Dobbs, Tomasz Nowicki, Maxim Sviridenko, Grzegorz Swirszcz, and Neal E. Young. Approximation algorithms for the joint replenishment problem with deadlines. Journal of Scheduling, 18(6):545-560, 2015. Google Scholar
  6. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Dorian Nogneng, and Jiří Sgall. Better approximation bounds for the joint replenishment problem. In Proc. 25th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 42-54, 2014. Google Scholar
  7. Marcin Bienkowski, Jaroslaw Byrka, Marek Chrobak, Łukasz Jeż, Jiří Sgall, and Grzegorz Stachowiak. Online control message aggregation in chain networks. In Proc. 13th Int. Workshop on Algorithms and Data Structures (WADS), pages 133-145, 2013. Google Scholar
  8. Edward Bortnikov and Reuven Cohen. Schemes for scheduling of control messages by hierarchical protocols. In Proc. 17th IEEE Int. Conference on Computer Communications (INFOCOM), pages 865-872, 1998. Google Scholar
  9. Carlos Brito, Elias Koutsoupias, and Shailesh Vaya. Competitive analysis of organization networks or multicast acknowledgement: How much to wait? Algorithmica, 64(4):584-605, 2012. Google Scholar
  10. Niv Buchbinder, Tracy Kimbrel, Retsef Levi, Konstantin Makarychev, and Maxim Sviridenko. Online make-to-order joint replenishment model: Primal-dual competitive algorithms. In Proc. 19th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 952-961, 2008. Google Scholar
  11. Niv Buchbinder and Joseph (Seffi) Naor. The design of competitive online algorithms via a primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3):93-263, 2009. Google Scholar
  12. Marek Chrobak, Claire Kenyon, John Noga, and Neal E. Young. Incremental medians via online bidding. Algorithmica, 50(4):455-478, 2008. Google Scholar
  13. Marek Chrobak and Claire Kenyon-Mathieu. SIGACT news online algorithms column 10: competitiveness via doubling. SIGACT News, 37(4):115-126, 2006. Google Scholar
  14. Wallace B. Crowston and Michael H. Wagner. Dynamic lot size models for multi-stage assembly systems. Management Science, 20(1):14-21, 1973. Google Scholar
  15. Daniel R. Dooly, Sally A. Goldman, and Stephen D. Scott. On-line analysis of the TCP acknowledgment delay problem. Journal of the ACM, 48(2):243-273, 2001. Google Scholar
  16. Fei Hu, Xiaojun Cao, and C. May. Optimized scheduling for data aggregation in wireless sensor networks. In Int. Conference on Information Technology: Coding and Computing (ITCC), volume 2, pages 557-561, 2005. Google Scholar
  17. Anna R. Karlin, Claire Kenyon, and Dana Randall. Dynamic TCP acknowledgement and other stories about e/(e - 1). Algorithmica, 36(3):209-224, 2003. Google Scholar
  18. Sanjeev Khanna, Joseph Naor, and Danny Raz. Control message aggregation in group communication protocols. In Proc. 29th Int. Colloq. on Automata, Languages and Programming (ICALP), pages 135-146, 2002. Google Scholar
  19. Alf Kimms. Multi-Level Lot Sizing and Scheduling: Methods for Capacitated, Dynamic, and Deterministic Models. Springer-Verlag, 1997. Google Scholar
  20. Douglas M Lambert and Martha C Cooper. Issues in supply chain management. Industrial Marketing Management, 29(1):65-83, 2000. Google Scholar
  21. Retsef Levi, Robin Roundy, and David B. Shmoys. A constant approximation algorithm for the one-warehouse multi-retailer problem. In Proc. 16th ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 365-374, 2005. Google Scholar
  22. Retsef Levi, Robin Roundy, and David B. Shmoys. Primal-dual algorithms for deterministic inventory problems. Mathematics of Operations Research, 31(2):267-284, 2006. Google Scholar
  23. Retsef Levi, Robin Roundy, David B. Shmoys, and Maxim Sviridenko. A constant approximation algorithm for the one-warehouse multiretailer problem. Management Science, 54(4):763-776, 2008. Google Scholar
  24. Retsef Levi and Maxim Sviridenko. Improved approximation algorithm for the one-warehouse multi-retailer problem. In Proc. 9th Int. Workshop on Approximation Algorithms for Combinatorial Optimization (APPROX), pages 188-199, 2006. Google Scholar
  25. Tim Nonner and Alexander Souza. Approximating the joint replenishment problem with deadlines. Discrete Mathematics, Algorithms and Applications, 1(2):153-174, 2009. Google Scholar
  26. Christos Papadimitriou. Computational aspects of organization theory. In Proc. 4th European Symp. on Algorithms (ESA), pages 559-564, 1996. Google Scholar
  27. Lehilton L. C. Pedrosa. Private communication. 2013. Google Scholar
  28. Steven S. Seiden. A guessing game and randomized online algorithms. In Proc. 32nd ACM Symp. on Theory of Computing (STOC), pages 592-601, 2000. Google Scholar
  29. Shailesh Vaya. Brief announcement: Delay or deliver dilemma in organization networks. In Proc. 31st ACM Symp. on Principles of Distributed Computing (PODC), pages 339-340, 2012. Google Scholar
  30. H.M. Wagner and T. Whitin. Dynamic version of the economic lot size model. Management Science, 5:89-96, 1958. Google Scholar
  31. Wei Yuan, Srikanth V. Krishnamurthy, and Satish K. Tripathi. Synchronization of multiple levels of data fusion in wireless sensor networks. In Proc. Global Telecommunications Conference (GLOBECOM), pages 221-225, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact