Online Generalized Network Design Under (Dis)Economies of Scale

References

• [1] Agrawal A, Klein PN, Ravi R (1995) When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24(3):440–456.Crossref, Google Scholar
• [2] Alon N, Awerbuch B, Azar Y, Buchbinder N, Naor J (2006) A general approach to online network optimization problems. ACM Trans. Algorithms 2(4):640–660.Crossref, Google Scholar
• [3] Alon N, Awerbuch B, Azar Y, Buchbinder N, Naor J (2009) The online set cover problem. SIAM J. Comput. 39(2):361–370.Crossref, Google Scholar
• [4] Anand S, Garg N, Kumar A (2012) Resource augmentation for weighted flow-time explained by dual fitting. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms, 1228–1241.Google Scholar
• [5] Andrews M, Antonakopoulos S, Zhang L (2016) Minimum-cost network design with (dis)economies of scale. SIAM J. Comput. 45(1):49–66.Crossref, Google Scholar
• [6] Andrews M, Anta AF, Zhang L, Zhao W (2012) Routing for power minimization in the speed scaling model. IEEE/ACM Trans. Networking 20(1):285–294.Crossref, Google Scholar
• [7] Antoniadis A, Im S, Krishnaswamy R, Moseley B, Nagarajan V, Pruhs K, Stein C (2020) Hallucination helps: Energy efficient virtual circuit routing. SIAM J. Comput. 49(1):37–66.Crossref, Google Scholar
• [8] Awerbuch B, Azar Y (1997) Buy-at-bulk network design. 38th Annual Sympos. Foundations Comput. Sci., 542–547.Google Scholar
• [9] Awerbuch B, Azar Y, Grove EF, Kao M, Krishnan P, Vitter JS (1995) Load balancing in the lp norm. 36th Annual Sympos. Foundations Comput. Sci., 383–391.Google Scholar
• [10] Azar Y, Epstein A (2005) Convex programming for scheduling unrelated parallel machines. Proc. 37th Annual ACM Sympos. Theory Comput., 331–337.Google Scholar
• [11] Azar Y, Buchbinder N, Chan TH, Chen S, Cohen IR, Gupta A, Huang Z, et al. (2016) Online algorithms for covering and packing problems with convex objectives. IEEE 57th Annual Sympos. Foundations Comput. Sci., 148–157.Google Scholar
• [12] Bansal N, Buchbinder N, Naor J (2012) A primal-dual randomized algorithm for weighted paging. J. ACM 59(4):1–24.Crossref, Google Scholar
• [13] Bansal N, Gupta A, Krishnaswamy R, Nagarajan V, Pruhs K, Stein C (2012) Multicast routing for energy minimization using speed scaling. Even G, Rawitz D, eds. Design Anal. Algorithms—First Mediterranean Conf. Algorithms, 37–51.Google Scholar
• [14] Buchbinder N, Naor J (2009) The design of competitive online algorithms via a primal-dual approach. Foundations Trends Theoret. Comput. Sci. 3(2–3): 93–263. Google Scholar
• [15] Byrka J, Grandoni F, Rothvoß T, Sanità L (2013) Steiner tree approximation via iterative randomized rounding. J. ACM 60(1):1–33.Crossref, Google Scholar
• [16] Caragiannis I (2008) Better bounds for online load balancing on unrelated machines. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 972–981.Google Scholar
• [17] Chakrabarty D, Ene A, Krishnaswamy R, Panigrahi D (2018) Online buy-at-bulk network design. SIAM J. Comput. 47(4):1505–1528.Crossref, Google Scholar
• [18] Charikar M, Chekuri C, Cheung T, Dai Z, Goel A, Guha S, Li M (1999) Approximation algorithms for directed Steiner problems. J. Algorithms 33(1):73–91.Crossref, Google Scholar
• [19] Chekuri C, Even G, Gupta A, Segev D (2011) Set connectivity problems in undirected graphs and the directed Steiner network problem. ACM Trans. Algorithms 7(2):1–17.Crossref, Google Scholar
• [20] Chekuri C, Hajiaghayi MT, Kortsarz G, Salavatipour MR (2010) Approximation algorithms for nonuniform buy-at-bulk network design. SIAM J. Comput. 39(5):1772–1798.Crossref, Google Scholar
• [21] Devanur NR, Huang Z (2018) Primal dual gives almost optimal energy-efficient online algorithms. ACM Trans. Algorithms 14(1):1–30.Crossref, Google Scholar
• [22] Dodis Y, Khanna S (1999) Design networks with bounded pairwise distance. Proc. 31st Annual ACM Sympos. Theory Comput. (ACM, New York), 750–759.Google Scholar
• [23] Emek Y, Kutten S, Lavi R, Shi Y (2020) Approximating generalized network design under (dis)economies of scale with applications to energy efficiency. J. ACM 67(1):1–33.Crossref, Google Scholar
• [24] Emek Y, Kutten S, Lavi R, Shi Y (2020) Personal communication.Google Scholar
• [25] Faloutsos M, Pankaj R, Sevcik KC (2002) The effect of asymmetry on the on-line multicast routing problem. Internat. J. Foundations Comput. Sci. 13(6):889–910.Crossref, Google Scholar
• [26] Feldman M, Kortsarz G, Nutov Z (2012) Improved approximation algorithms for directed steiner forest. J. Comput. System Sci. 78(1):279–292.Crossref, Google Scholar
• [27] Ghuge R, Nagarajan V (2022) Quasi-polynomial algorithms for submodular tree orienteering and other directed network design problems. Math. Oper. Res. 47(2):1612–1630.Google Scholar
• [28] Goemans MX, Williamson DP (1995) A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2):296–317.Crossref, Google Scholar
• [29] Grandoni F, Laekhanukit B, Li S (2019) O(log2k/log logk)-approximation algorithm for directed Steiner tree: A tight quasi-polynomial-time algorithm. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (ACM, New York), 253–264.Google Scholar
• [30] Gupta A, Krishnaswamy R, Pruhs K (2012) Online primal-dual for non-linear optimization with applications to speed scaling. 10th Internat. Workshop Approximation Online Algorithms, 173–186.Google Scholar
• [31] Huang Z, Kim A (2019) Welfare maximization with production costs: A primal dual approach. Games Econom. Behav. 118:648–667.Crossref, Google Scholar
• [32] Krishnaswamy R, Nagarajan V, Pruhs K, Stein C (2014) Cluster before you hallucinate: Approximating node-capacitated network design and energy efficient routing. Proc. 46th ACM Sympos. Theory Comput. (ACM, New York), 734–743.Google Scholar
• [33] Makarychev K, Sviridenko M (2018) Solving optimization problems with diseconomies of scale via decoupling. J. ACM 65(6):1–27.Crossref, Google Scholar
• [34] Roughgarden T (2015) Intrinsic robustness of the price of anarchy. J. ACM 62(5):1–42.Crossref, Google Scholar
• [35] Shen X, Nagarajan V (2020) Online covering with lq-norm objectives and applications to network design. Math. Programming 184(1):155–182.Crossref, Google Scholar
• [36] Wierman A, Andrew LLH, Tang A (2012) Power-aware speed scaling in processor sharing systems: Optimality and robustness. Performance Evaluation 69(12):601–622.Crossref, Google Scholar