Overcommitment in Cloud Services: Bin Packing with Chance Constraints

References

• Abdelaziz FB, Aouni B, El Fayedh R (2007) Multi-objective stochastic programming for portfolio selection. Eur. J. Oper. Res. 177(3):1811–1823.Crossref, Google Scholar
• Albers S, Souza A (2011) Combinatorial algorithms lecture notes: Bin packing. Accessed August 1, 2017, https://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/bin_packing.pdf.Google Scholar
• Atamtürk A, Narayanan V (2008) Polymatroids and mean-risk minimization in discrete optimization. Oper. Res. Lett. 36(5):618–622.Crossref, Google Scholar
• Bays C (1977) A comparison of next-fit, first-fit, and best-fit. Comm. ACM 20(3):191–192.Crossref, Google Scholar
• Bertsimas D, Popescu I (2005) Optimal inequalities in probability theory: A convex optimization approach. SIAM J. Optim. 15(3):780–804.Crossref, Google Scholar
• Calafiore GC, El Ghaoui L (2006) On distributionally robust chance-constrained linear programs. J. Optim. Theory Appl. 130(1):1–22.Crossref, Google Scholar
• Cardoen B, Demeulemeester E, Beliën J (2010) Operating room planning and scheduling: A literature review. Eur. J. Oper. Res. 201(3):921–932.Crossref, Google Scholar
• Charnes A, Cooper WW (1963) Deterministic equivalents for optimizing and satisfying under chance constraints. Oper. Res. 11(1):18–39.Link, Google Scholar
• Coffman EG Jr, Garey MR, Johnson DS (1996) Approximation algorithms for bin packing: A survey. Approximation Algorithms for NP-Hard Problems (PWS Publishing Co., Boston), 46–93.Google Scholar
• Coffman EG Jr, So K, Hofri M, Yao A (1980) A stochastic model of bin-packing. Inform. Control 44(2):105–115.Crossref, Google Scholar
• Csirik J, Johnson DS, Kenyon C, Orlin JB, Shor PW, Weber RR (2006) On the sum-of-squares algorithm for bin packing. J. ACM 53(1):1–65.Crossref, Google Scholar
• Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper. Res. 58(3):595–612.Link, Google Scholar
• de La Vega WF, Lueker GS (1981) Bin packing can be solved within 1+ ϵ in linear time. Combinatorica 1(4):349–355.Crossref, Google Scholar
• Delorme M, Iori M, Martello S (2016) Bin packing and cutting stock problems: Mathematical models and exact algorithms. Eur. J. Oper. Res. 255(1):1–20.Crossref, Google Scholar
• Deng Y, Shen S, Denton B (2016) Chance-constrained surgery planning under conditions of limited and ambiguous data. Working paper, University of Michigan, Ann Arbor.Google Scholar
• Denton BT, Miller AJ, Balasubramanian HJ, Huschka TR (2010) Optimal allocation of surgery blocks to operating rooms under uncertainty. Oper. Res. 58(4, part 1):802–816.Link, Google Scholar
• Dinh HT, Lee C, Niyato D, Wang P (2013) A survey of mobile cloud computing: Architecture, applications, and approaches. Wireless Comm. Mobile Comput. 13(18):1587–1611.Crossref, Google Scholar
• Dósa G (2007) The tight bound of first fit decreasing bin-packing algorithm is ffd≤11/9opt+6/9. Combinatorics, Algorithms, Probabilistic and Experimental Methodologies (Springer, Berlin), 1–11.Crossref, Google Scholar
• Dósa G, Sgall J (2013) First fit bin packing: A tight analysis. Portier N, Wilke T, eds. LIPIcs-Leibniz Internat. Proc. Informatics (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl Publishing, Germany), 538–549.Google Scholar
• El Ghaoui L, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Oper. Res. 51(4):543–556.Link, Google Scholar
• Fox A, Griffith R, Joseph A, Katz R, Konwinski A, Lee G, Patterson D, Rabkin A, Stoica I (2009) Above the clouds: A Berkeley view of cloud computing. Report No. UCB/EECS 28(13):2009, Department Electrical Engineering and Computer Sciences, University of California, Berkeley.Google Scholar
• Gilmore PC, Gomory RE (1961) A linear programming approach to the cutting-stock problem. Oper. Res. 9(6):849–859.Link, Google Scholar
• Goemans MX, Harvey NJ, Iwata S, Mirrokni V (2009) Approximating submodular functions everywhere. Mathieu C, ed. Proc. 20th Ann. ACM-SIAM Sympos. on Discrete Algorithms (Brown University, Providence, RI), 535–544.Crossref, Google Scholar
• Goyal V, Ravi R (2010) A PTAS for the chance-constrained knapsack problem with random item sizes. Oper. Res. Lett. 38(3):161–164.Crossref, Google Scholar
• Gupta V, Radovanovic A (2015) Lagrangian-based online stochastic bin packing. ACM SIGMETRICS Perform. Eval. Rev. 43(1):467–468.Crossref, Google Scholar
• Han J, Lee K, Lee C, Choi KS, Park S (2016) Robust optimization approach for a chance-constrained binary knapsack problem. Math. Programming 157(1):277–296.Crossref, Google Scholar
• Johnson DS (1974) Fast algorithms for bin packing. J. Comput. System Sci. 8(3):272–314.Crossref, Google Scholar
• Keller G, Tighe M, Lutfiyya H, Bauer M (2012) An analysis of first fit heuristics for the virtual machine relocation problem. Lobo J, Owezarski P, Zhang H, Medhi D, eds. Proc. 8th Internat. Conf. Network Service Management (IEEE, New York), 406–413.Google Scholar
• Kenyon C, et al.. (1996) Best-fit bin-packing with random order. Proc. 7th Ann. ACM-SIAM Sympos. Discrete Algorithms (SODA), (Society for Industrial and Applied Mathematics, Philadelphia), 359–364.Google Scholar
• Kim U (2015) This one chart shows the vicious price war going on in Cloud computing. Bus. Insider (January 14), http://www.businessinsider.com/cloud-computing-price-war-in-one-chart-2015-1.Google Scholar
• Kleinberg J, Rabani Y, Tardos É (2000) Allocating bandwidth for bursty connections. SIAM J. Comput. 30(1):191–217.Crossref, Google Scholar
• Lee S, Panigrahy R, Prabhakaran V, Ramasubramanian V, Talwar K, Uyeda L, Wieder U (2011) Validating heuristics for virtual machines consolidation. Technical Report, Microsoft Research Silicon Valley, Mountain View, CA.Google Scholar
• Luedtke J, Ahmed S, Nemhauser GL (2010) An integer programming approach for linear programs with probabilistic constraints. Math. Programming 122(2):247–272.Crossref, Google Scholar
• Lueker GS (1983) Bin packing with items uniformly distributed over intervals [a, b]. Proc. 24th Ann. Sympos. Foundations Computer Sci. (IEEE, New York), 289–297.Crossref, Google Scholar
• Nemirovski A, Shapiro A (2006) Convex approximations of chance constrained programs. SIAM J Optim. 17(4):969–996.Crossref, Google Scholar
• Pisinger D, Sigurd M (2005) The two-dimensional bin packing problem with variable bin sizes and costs. Discrete Optim. 2(2):154–167.Crossref, Google Scholar
• Roytman A, Kansal A, Govindan S, Liu J, Nath S (2013) Algorithm design for performance aware vm consolidation. Technical Report, Microsoft Research, Redmond, WA.Google Scholar
• Shylo OV, Prokopyev OA, Schaefer AJ (2012) Stochastic operating room scheduling for high-volume specialties under block booking. INFORMS J. Comput. 25(4):682–692.Link, Google Scholar
• Stolyar AL, Zhong Y (2015) Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints. Queueing Systems 79(2):117–143.Crossref, Google Scholar
• Svitkina Z, Fleischer L (2011) Submodular approximation: Sampling-based algorithms and lower bounds. SIAM J Comput. 40(6):1715–1737.Crossref, Google Scholar
• Verma A, Pedrosa L, Korupolu MR, Oppenheimer D, Tune E, Wilkes J (2015) Large-scale cluster management at Google with Borg. Proc. European Conf. Computer Systems (EuroSys, Bordeaux, France), 1–17.Crossref, Google Scholar
• Zhang Y, Jiang R, Shen S (2016) Distributionally robust chance-constrained bin packing. Working paper, University of Michigan, Ann Arbor.Google Scholar