Online Algorithms for Multilevel Aggregation

References

• Aggarwal A, Park JK (1993) Improved algorithms for economic lot sizing problems. Oper. Res. 41(3):549–571.Link, Google Scholar
• Albers S, Bals H (2005) Dynamic TCP acknowledgment: Penalizing long delays. SIAM J. Discrete Math. 19(4):938–951.Crossref, Google Scholar
• Arkin E, Joneja D, Roundy R (1989) Computational complexity of uncapacitated multi-echelon production planning problems. Oper. Res. Lett. 8(2):61–66.Crossref, Google Scholar
• Azar Y, Epstein A, Jeż Ł, Vardi A (2016) Make-to-order integrated scheduling and distribution. Proc. 24th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 140–154.Crossref, Google Scholar
• Azar Y, Ganesh A, Ge R, Panigrahi D (2017) Online service with delay. Proc. 49th ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 551–563.Crossref, Google Scholar
• Badrinath BR, Sudame P (2000) Gathercast: The design and implementation of a programmable aggregation mechanism for the internet. Proc. Ninth Internat. Conf. Comput. Comm. Networks (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 206–213.Crossref, Google Scholar
• Bartal Y (1996) Probabilistic approximations of metric spaces and its algorithmic applications. Proc. 37th IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 184–193.Crossref, Google Scholar
• Becchetti L, Marchetti-Spaccamela A, Vitaletti A, Korteweg P, Skutella M, Stougie L (2009) Latency-constrained aggregation in sensor networks. ACM Trans. Algorithms 6(1):13:1–13:20.Crossref, Google Scholar
• Bienkowski M, Byrka J, Chrobak M, Jeż Ł, Nogneng D, Sgall J (2014) Better approximation bounds for the joint replenishment problem. Proc. 25th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 42–54.Crossref, Google Scholar
• Bienkowski M, Byrka J, Chrobak M, Jeż Ł, Sgall J, Stachowiak G (2013) Online control message aggregation in chain networks. Proc. 13th Internat. Workshop Algorithms Data Structures (Springer-Verlag, Berlin), 133–145.Crossref, Google Scholar
• Bienkowski M, Byrka J, Chrobak M, Dobbs NB, Nowicki T, Sviridenko M, Swirszcz G, Young NE (2015) Approximation algorithms for the joint replenishment problem with deadlines. J. Scheduling 18(6):545–560.Crossref, Google Scholar
• Bienkowski M, Böhm M, Byrka J, Chrobak M, Dürr C, Folwarczný L, Jeż Ł, Sgall J, Thang NK, Veselý P (2016) Online algorithms for multi-level aggregation. Proc. 24th Eur. Sympos. Algorithms (Springer-Verlag, Berlin), 12:1–12:17.Google Scholar
• Borodin A, El-Yaniv R (1998) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Bortnikov E, Cohen R (1998) Schemes for scheduling of control messages by hierarchical protocols. Proc. 17th IEEE Internat. Conf. Comput. Comm. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 865–872.Crossref, Google Scholar
• Brito C, Koutsoupias E, Vaya S (2012) Competitive analysis of organization networks or multicast acknowledgement: How much to wait? Algorithmica 64(4):584–605.Crossref, Google Scholar
• Buchbinder N, Naor JS (2009) The design of competitive online algorithms via a primal-dual approach. Foundations Trends Theoret. Comput. Sci. 3(2–3):93–263.Crossref, Google Scholar
• Buchbinder N, Feldman M, Naor JS, Talmon O (2017) O(depth)-competitive algorithm for online multi-level aggregation. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1235–1244.Crossref, Google Scholar
• Buchbinder N, Kimbrel T, Levi R, Makarychev K, Sviridenko M (2008) Online make-to-order joint replenishment model: Primal-dual competitive algorithms. Proc. 19th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 952–961.Google Scholar
• Crowston WB, Wagner MH (1973) Dynamic lot size models for multi-stage assembly systems. Management Sci. 20(1):14–21.Link, Google Scholar
• Dooly DR, Goldman SA, Scott SD (2001) On-line analysis of the TCP acknowledgment delay problem. J. ACM 48(2):243–273.Crossref, Google Scholar
• Frederiksen JS, Larsen KS, Noga J, Uthaisombut P (2003) Dynamic TCP acknowledgment in the LogP model. J. Algorithms 48(2):407–428.Crossref, Google Scholar
• Hu F, Cao X, May C (2005) Optimized scheduling for data aggregation in wireless sensor networks. Internat. Conf. Inform. Tech. Coding Comput., vol. 2 (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 557–561.Crossref, Google Scholar
• Karlin AR, Kenyon C, Randall D (2003) Dynamic TCP acknowledgement and other stories about e/(e – 1). Algorithmica 36(3):209–224.Crossref, Google Scholar
• Khanna S, Naor J, Raz D (2002) Control message aggregation in group communication protocols. Proc. 29th internat. Colloquium Automata, Languages Programming (Springer-Verlag, Berlin), 135–146.Crossref, Google Scholar
• Kimms A (1997) Multi-Level Lot Sizing and Scheduling: Methods for Capacitated, Dynamic, and Deterministic Models (Springer-Verlag, Berlin).Crossref, Google Scholar
• Lambert DM, Cooper MC (2000) Issues in supply chain management. Indust. Marketing Management 29(1):65–83.Crossref, Google Scholar
• Levi R, Sviridenko M (2006) Improved approximation algorithm for the one-warehouse multi-retailer problem. Proc. Ninth Internat. Workshop Approximation Algorithms Combin. Optim. (Springer, Berlin), 188–199.Crossref, Google Scholar
• Levi R, Roundy R, Shmoys DB (2005) A constant approximation algorithm for the one-warehouse multi-retailer problem. Proc. 16th ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 365–374.Google Scholar
• Levi R, Roundy R, Shmoys DB (2006) Primal-dual algorithms for deterministic inventory problems. Math. Oper. Res. 31(2):267–284.Link, Google Scholar
• Levi R, Roundy R, Shmoys DB, Sviridenko M (2008) A constant approximation algorithm for the one-warehouse multiretailer problem. Management Sci. 54(4):763–776.Link, Google Scholar
• Nonner T, Souza A (2009) Approximating the joint replenishment problem with deadlines. Discrete Math. Algorithms Appl. 1(2):153–174.Crossref, Google Scholar
• Papadimitriou C (1996) Computational aspects of organization theory. Proc. 4th Eur. Sympos. Algorithms (Springer-Verlag, Berlin), 559–564.Crossref, Google Scholar
• Pedrosa LLC (2013) Personal communication.Google Scholar
• Seiden SS (2000) A guessing game and randomized online algorithms. Proc. 32nd ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 592–601.Crossref, Google Scholar
• Sgall J (1998) On-line scheduling. Online Algorithms: The State of the Art (Springer, Berlin), 196–231.Crossref, Google Scholar
• Vaya S (2012) Brief announcement: Delay or deliver dilemma in organization networks. Proc. 31st ACM Sympos. Principles Distributed Comput. (Association for Computing Machinery, New York), 339–340.Crossref, Google Scholar
• Wagner H, Whitin T (1958) Dynamic version of the economic lot size model. Management Sci. 5(1):89–96.Link, Google Scholar
• Yuan W, Krishnamurthy SV, Tripathi SK (2003) Synchronization of multiple levels of data fusion in wireless sensor networks. Proc. Global Telecomm. Conf. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 221–225.Google Scholar