A Service System with Packing Constraints: Greedy Randomized Algorithm Achieving Sublinear in Scale Optimality Gap

References

• Bansal N , Caprara A , Sviridenko M (2009) A new approximation method for set covering problems, with applications to multidimensional bin packing. SIAM J. Comput. 39(4):1256–1278.Google Scholar
• Chekuri C , Khanna S (2004) On multidimensional packing problems. SIAM J. Comput. 33(4):837–851.Google Scholar
• Coffman EG Jr , Stolyar AL (2001) Bandwidth packing. Algorithmica 29(1–2):70–88.Google Scholar
• Coffman EG Jr , Garey MR , Johnson DS (1983) Dynamic bin packing. SIAM J. Comput. 12(2):227–258.Google Scholar
• Coffman EG Jr , Csirik J , Galambos G , Martello S , Vigo D (2013) Bin packing approximation algorithms: Survey and classification. Pardalos PM , Du DZ , Graham RL , eds. Handbook of Combinatorial Optimization (Springer, New York), 455–531.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.Google Scholar
• Gamarnik D (2004) Stochastic bandwidth packing process: Stability conditions via Lyapunov function technique. Queueing Systems 48:339–363.Google Scholar
• Ghaderi J, Zhong Y, Srikant R (2014) Asymptotic optimality of best-fit for stochastic bin packing. ACM SIGMETRICS Performance Eval. Rev. 42(2):64–66.Google Scholar
• Gulati A , Holler A , Ji M , Shanmuganathan G , Waldspurger C , Zhu X (2012) VMware distributed resource management: Design, implementation and lessons learned. VMware Tech. J. 1(1):45–64.Google Scholar
• Guo Y, Stolyar AL, Walid A (2015) Shadow-routing based dynamic algorithms for virtual machine placement in a network cloud. IEEE Trans. Cloud Comput. 6(1):209–220. Google Scholar
• Gupta V , Radovanovic A (2012) Online stochastic bin packing. Preprint, submitted November 12, https://arxiv.org/abs/1211.2687.Google Scholar
• Jiang JW , Lan T , Ha S , Chen M , Chiang M (2012) Joint VM placement and routing for data center traffic engineering. 2012 Proc. IEEE INFOCOM, 2876–2880.Google Scholar
• Liptser RS , Shiryaev AN (1989) Theory of Martingales (Kluwer Academic Publishers, Dordrecht, Netherlands).Google Scholar
• Maguluri ST , Srikant R (2013) Scheduling jobs with unknown duration in clouds. IEEE/ACM Trans. Networking 22(6):1938–1951.Google Scholar
• Maguluri ST , Srikant R , Ying L (2012) Stochastic models of load balancing and scheduling in cloud computing clusters. 2012 Proc. IEEE INFOCOM, 702–710.Google Scholar
• Mitzenmacher M , Upfal E (2005) Probability and Computing: Randomized Algorithms and Probabilistic Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Pang G , Talreja R , Whitt W (2007) Martingale proofs of many-server heavy-traffic limits for Markovian queues. Probab. Surveys 4:193–267.Google Scholar
• Stolyar AL (2013) An infinite server system with general packing constraints. Oper. Res. 61(5):1200–1217.Link, Google Scholar
• Stolyar AL (2017) Large-scale heterogeneous service systems with general packing constraints. Adv. Appl. Probab. 49(1):61–83.Google Scholar
• Stolyar AL , Zhong Y (2013) A large-scale service system with packing constraints: Minimizing the number of occupied servers. ACM SIGMETRICS Performance Eval. Rev. 41(1):41–52.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.Google Scholar