Online Rack Placement in Large-Scale Data Centers: Online Sampling Optimization and Deployment

References

• ADW Developments (2025) Technical information paper: Embodied carbon in enterprise data centre IT equipment. Accessed December 26, 2025, https://adwdevelopments.com/sustainability/technical-information-paper-embodied-carbon-in-enterprise-data-centre-it-equipment/.Google Scholar
• Agrawal S, Devanur NR (2015) Fast algorithms for online stochastic convex programming. Indyk P, ed. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1405–1424.Google Scholar
• Arbabian ME, Chen S, Moinzadeh K (2021) Capacity expansions with bundled supplies of attributes: An application to server procurement in cloud computing. Manufacturing Service Oper. Management 23(1):191–209.Link, Google Scholar
• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multisecretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Arlotto A, Xie X (2020) Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards. Stochastic Systems 10(2):170–191.Link, Google Scholar
• Aterio (2026) Data centers from Microsoft. Accessed January 12, 2026, https://www.aterio.io/us-data-centers/providers/0820543f-b9ae-43de-8887-751f944d38a3.Google Scholar
• Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1358–1377.Google Scholar
• Balseiro SR, Besbes O, Pizarro D (2024) Survey of dynamic resource-constrained reward collection problems: Unified model and analysis. Oper. Res. 72(5):2168–2189.Link, Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2023) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Banerjee S, Freund D (2024) Good prophets know when the end is near. Management Sci. 71(6):4877–4894.Link, Google Scholar
• Bertsekas D (2012) Dynamic Programming and Optimal Control, 4th ed., vol. I (Athena Scientific, Nashua, NH).Google Scholar
• Bertsimas D, Mundru N (2022) Optimization-based scenario reduction for data-driven two-stage stochastic optimization. Oper. Res. 71(4):1343–1361.Link, Google Scholar
• Besbes O, Kanoria Y, Kumar A (2022) The multi-secretary problem with many types. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 1146–1147.Google Scholar
• Bodur M, Luedtke JR (2022) Two-stage linear decision rules for multi-stage stochastic programming. Math. Programming 191(1):347–380.Crossref, Google Scholar
• Bray RL (2024) Logarithmic regret in multisecretary and online linear programs with continuous valuations. Oper. Res. 73(4):2188–2203.Link, Google Scholar
• Bray RL, Coviello D, Ichino A, Persico N (2016) Multitasking, multiarmed bandits, and the Italian judiciary. Manufacturing Service Oper. Management 18(4):545–558.Link, Google Scholar
• Buchbinder N, Fairstein Y, Mellou K, Menache I, Naor JS (2022) Online virtual machine allocation with lifetime and load predictions. SIGMETRICS Performance Evaluation Rev. 49(1):9–10.Crossref, Google Scholar
• Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Sci. 66(7):2993–3009.Link, Google Scholar
• Caramanis C, Dütting P, Faw M, Fusco F, Lazos P, Leonardi S, Papadigenopoulos O, Pountourakis E, Reiffenhäuser R (2022) Single-sample prophet inequalities via greedy-ordered selection. Naor J, Buchbinder N, eds. Proc. 2022 Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 1298–1325.Google Scholar
• Chen Y, Farias VF (2013) Simple policies for dynamic pricing with imperfect forecasts. Oper. Res. 61(3):612–624.Link, Google Scholar
• Chen Y, Wang W (2025) Beyond non-degeneracy: Revisiting certainty equivalent heuristic for online linear programming. Preprint, submitted January 3, https://arxiv.org/abs/2501.01716v1.Google Scholar
• Chen Y, Kanoria Y, Kumar A, Zhang W (2023b) Feature-based dynamic matching. Preprint, submitted May 18, http://dx.doi.org/10.2139/ssrn.4451799.Google Scholar
• Chen S, Moinzadeh K, Song JS, Zhong Y (2023a) Cloud computing value chains: Research from the operations management perspective. Manufacturing Service Oper. Management 25(4):1338–1356.Link, Google Scholar
• Ciocan DF, Farias V (2012) Model predictive control for dynamic resource allocation. Math. Oper. Res. 37(3):501–525.Link, Google Scholar
• Cohen MC, Jacquillat A, Serpa JC, Benborhoum M (2023) Managing airfares under competition: Insights from a field experiment. Management Sci. 69(10):6076–6108.Link, Google Scholar
• Cohen MC, Keller PW, Mirrokni V, Zadimoghaddam M (2019) Overcommitment in cloud services: Bin packing with chance constraints. Management Sci. 65(7):3255–3271.Link, Google Scholar
• Cooper WL (2002) Asymptotic behavior of an allocation policy for revenue management. Oper. Res. 50(4):720–727.Link, Google Scholar
• Daryalal M, Bodur M, Luedtke JR (2024) Lagrangian dual decision rules for multistage stochastic mixed-integer programming. Oper. Res. 72(2):717–737.Link, Google Scholar
• Data Center Knowledge (2022) Data center hardware refresh cutback by Microsoft. Accessed December 22, 2025, https://www.datacenterknowledge.com/hyperscalers/data-center-hardware-refresh-cutback-by-microsoft-what-s-next-.Google Scholar
• Devenur NR, Hayes TP (2009) The adwords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York).Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. Berg M, Meyer U, eds. Proc. 18th Annual Eur. Conf. Algorithms, Part I (Springer-Verlag, Berlin), 182–194.Google Scholar
• Freund D, Zhao J (2021) Overbooking with bounded loss. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 477–478.Google Scholar
• Gade D, Hackebeil G, Ryan SM, Watson JP, Wets RJB, Woodruff DL (2016) Obtaining lower bounds from the progressive hedging algorithm for stochastic mixed-integer programs. Math. Programming 157(1):47–67.Crossref, Google Scholar
• Gallego G, Van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Sci. 40(8):999–1020.Link, Google Scholar
• Gallego G, Van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to network yield management. Oper. Res. 45(1):24–41.Link, Google Scholar
• Gardner K, Harchol-Balter M, Scheller-Wolf A, Velednitsky M, Zbarsky S (2017) Redundancy-d: The power of d choices for redundancy. Oper. Res. 65(4):1078–1094.Link, Google Scholar
• Grosof I, Scully Z, Harchol-Balter M, Scheller-Wolf A (2022) Optimal scheduling in the multiserver-job model under heavy traffic. Proc. ACM Measurement Anal. Comput. Systems 6(3):1–32.Crossref, Google Scholar
• Guan Y, Ahmed S, Nemhauser GL (2009) Cutting planes for multistage stochastic integer programs. Oper. Res. 57(2):287–298.Link, Google Scholar
• Gupta A, Molinaro M (2016) How the experts algorithm can help solve LPs online. Math. Oper. Res. 41(4):1404–1431.Link, Google Scholar
• Gupta V, Radovanovic A (2020) Interior-point-based online stochastic bin packing. Oper. Res. 68(5):1474–1492.Link, Google Scholar
• International Energy Agency (2022) Infrastructure deep dive: Data centres and data transmission networks. Technical report, International Energy Agency, Paris.Google Scholar
• Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Jasin S, Kumar S (2013) Analysis of deterministic LP-based booking limit and bid price controls for revenue management. Oper. Res. 61(6):1312–1320.Link, Google Scholar
• Jiang J, Ma W, Zhang J (2025) Degeneracy is OK: Logarithmic regret for network revenue management with indiscrete distributions. Oper. Res. 73(6):3405–3420.Link, Google Scholar
• Kesselheim T, Molinaro M (2020) Knapsack secretary with bursty adversary. Preprint, submitted June 20, https://arxiv.org/abs/2006.11607.Google Scholar
• Kesselheim T, Tönnis A, Radke K, Vöcking B (2014) Primal beats dual on online packing LPs in the random-order model. Proc. 46th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 303–312.Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Buchsbaum A, ed. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (SIAM, Philadelphia), 630–631.Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Kuhn D, Wiesemann W, Georghiou A (2011) Primal and dual linear decision rules in stochastic and robust optimization. Math. Programming 130(1):177–209.Crossref, Google Scholar
• Li X, Ye Y (2022) Online linear programming: Dual convergence, new algorithms, and regret bounds. Oper. Res. 70(5):2948–2966.Link, Google Scholar
• Liu S, Li X (2021) Online bin packing with known T. Preprint, submitted December 6, https://arxiv.org/abs/2112.03200.Google Scholar
• Liu RP, Mellou K, Gong XY, Li B, Coffee T, Pathuri J, Simchi-Levi D, Menache I (2023) Efficient cloud server deployment under demand uncertainty. Preprint, submitted July 3, http://dx.doi.org/10.2139/ssrn.4501810.Google Scholar
• Löhndorf N, Wozabal D, Minner S (2013) Optimizing trading decisions for hydro storage systems using approximate dual dynamic programming. Oper. Res. 61(4):810–823.Link, Google Scholar
• Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2):277–305.Crossref, Google Scholar
• Lulli G, Sen S (2004) A branch-and-price algorithm for multistage stochastic integer programming with application to stochastic batch-sizing problems. Management Sci. 50(6):786–796.Link, Google Scholar
• Lyu J, You M, Irvene C, Jung M, Narmore T, Shapiro J, Marshall L, et al. (2023) Hyrax: Fail-in-place server operation in cloud platforms. Proc. 17th Sympos. Operating Systems Design Implementation (OSDI) (USENIX, Berkeley, CA), 287–304.Google Scholar
• Maglaras C, Meissner J (2006) Dynamic pricing strategies for multiproduct revenue management problems. Manufacturing Service Oper. Management 8(2):136–148.Link, Google Scholar
• Mellou K, Molinaro M, Zhou R (2023) Online demand scheduling with failovers. Etessami K, Feige U, Puppis G, eds. 50th Internat. Colloquium Automata Languages Programming (ICALP 2023), vol. 261 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 92:1–92:20.Google Scholar
• Microsoft (2025a) Azure global infrastructure. Accessed December 26, 2025, https://azure.microsoft.com/en-us/explore/global-infrastructure.Google Scholar
• Microsoft (2025b) Inside the world’s most powerful AI datacenter. Accessed December 26, 2025, https://blogs.microsoft.com/blog/2025/09/18/inside-the-worlds-most-powerful-ai-datacenter/.Google Scholar
• Microsoft Datacenters (2025) The backbone of Microsoft Cloud: Our datacenters. Accessed December 22, 2025, https://datacenters.microsoft.com/.Google Scholar
• Molinaro M, Ravi R (2014) The geometry of online packing linear programs. Math. Oper. Res. 39(1):46–59.Link, Google Scholar
• Muir C, Marshall L, Toriello A (2024) Temporal bin packing with half-capacity jobs. INFORMS J. Optim. 6(1):46–62.Link, Google Scholar
• Natural Resources Defense Council (2014) Data center efficiency assessment. Technical report, Natural Resources Defense Council, New York.Google Scholar
• Pereira MV, Pinto LM (1991) Multi-stage stochastic optimization applied to energy planning. Math. Programming 52(1):359–375.Crossref, Google Scholar
• Perez-Salazar S, Singh M, Toriello A (2022) Adaptive bin packing with overflow. Math. Oper. Res. 47(4):3317–3356.Link, Google Scholar
• Philpott AB, Wahid F, Bonnans JF (2020) Midas: A mixed integer dynamic approximation scheme. Math. Programming 181(1):19–50.Crossref, Google Scholar
• Powell WB (2022) Reinforcement Learning and Stochastic Optimization: A Unified Framework for Sequential Decisions (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Radovanović A, Koningstein R, Schneider I, Chen B, Duarte A, Roy B, Xiao D, et al. (2022) Carbon-aware computing for datacenters. IEEE Trans. Power Systems 38(2):1270–1280.Crossref, Google Scholar
• Rao P (2024) Charted: How many data centers do major big tech companies have? Accessed December 22, 2025, https://www.visualcapitalist.com/charted-how-many-data-centers-do-major-big-tech-companies-have/.Google Scholar
• Reiman MI, Wang Q (2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Math. Oper. Res. 33(2):257–282.Link, Google Scholar
• Rhee WT, Talagrand M (1993a) On-line bin packing of items of random sizes, II. SIAM J. Comput. 22(6):1251–1256.Crossref, Google Scholar
• Rhee WT, Talagrand M (1993b) On line bin packing with items of random size. Math. Oper. Res. 18(2):438–445.Link, Google Scholar
• Rockafellar RT, Wets RJB (1991) Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1):119–147.Link, Google Scholar
• Römisch W (2009) Scenario reduction techniques in stochastic programming. Watanabe O, Zeugmann T, eds. Stochastic Algorithms Foundations Appl. SAGA 2009 (Springer, Berlin), 1–14.Google Scholar
• Rubinstein A, Wang JZ, Weinberg SM (2019) Optimal single-choice prophet inequalities from samples. Preprint, submitted November 18, https://arxiv.org/abs/1911.07945v1.Google Scholar
• Schroeder B, Wierman A, Harchol-Balter M (2006) Closed versus open system models: A cautionary tale. Proc. 3rd Conf. Networked Systems Design Implementation (USENIX Association, Berkeley, CA), 239–252.Google Scholar
• Secomandi N (2008) An analysis of the control-algorithm re-solving issue in inventory and revenue management. Manufacturing Service Oper. Management 10(3):468–483.Link, Google Scholar
• Stamatopoulos I, Bassamboo A, Moreno A (2021) The effects of menu costs on retail performance: Evidence from adoption of the electronic shelf label technology. Management Sci. 67(1):242–256.Link, Google Scholar
• Sutton RS, Barto AG (2018) Reinforcement Learning: An Introduction (MIT Press, Cambridge, MA).Google Scholar
• Uptime Institute (2014) Data center site infrastructure tier standard: Operational sustainability. Technical report, Uptime Institute, New York.Google Scholar
• Valério de Carvalho J (1999) Exact solution of bin-packing problems using column generation and branch-and-bound. Ann. Oper. Res. 86(0):629–659.Crossref, Google Scholar
• Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• Wu Q, Deng Q, Ganesh L, Hsu CH, Jin Y, Kumar S, Li B, Meza J, Song YJ (2016) Dynamo: Facebook’s data center-wide power management system. ACM SIGARCH Comput. Architecture News 44(3):469–480.Crossref, Google Scholar
• Xu H, Li B (2013) Joint request mapping and response routing for geo-distributed cloud services. 2013 Proc. IEEE INFOCOM (IEEE, New York), 854–862.Google Scholar
• Zhang W, Wang K, Jacquillat A, Wang S (2023) Optimized scenario reduction: Solving large-scale stochastic programs with quality guarantees. INFORMS J. Comput. 35(4):886–908.Link, Google Scholar
• Zhang C, Kumbhare AG, Manousakis I, Zhang D, Misra PA, Assis R, Woolcock K, et al. (2021) Flex: High-availability datacenters with zero reserved power. 2021 ACM/IEEE 48th Annual Internat. Sympos. Comput. Architecture (ISCA) (IEEE, New York), 319–332.Google Scholar
• Zou J, Ahmed S, Sun XA (2019) Stochastic dual dynamic integer programming. Math. Programming 175(1):461–502.Crossref, Google Scholar