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

DOI10.1287/stsy.2019.0067zbMath1492.90044arXiv1511.03241OpenAlexW3126383053MaRDI QIDQ5084484

Yuan Zhong, Alexander L. Stolyar

Publication date: 24 June 2022

Published in: Stochastic Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.03241

zbMATH Keywords

queueing networkscloud computingstochastic bin packinggreedy random (GRAND) algorithmpacking constraintssublinear optimality gap

Mathematics Subject Classification ID

Stochastic network models in operations research (90B15) Queueing theory (aspects of probability theory) (60K25) Queues and service in operations research (90B22) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30)

Cites Work

• Martingale proofs of many-server heavy-traffic limits for Markovian queues
• Stochastic bandwidth packing process: stability conditions via Lyapunov function technique
• Bandwidth packing
• Asymptotic optimality of a greedy randomized algorithm in a large-scale service system with general packing constraints
• On the Sum-of-Squares algorithm for bin packing
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• Dynamic Bin Packing
• On Multidimensional Packing Problems
• An Infinite Server System with General Packing Constraints
• Large-scale heterogeneous service systems with general packing constraints
• Probability and Computing

This page was built for publication: A Service System with Packing Constraints: Greedy Randomized Algorithm Achieving Sublinear in Scale Optimality Gap