Lagrangian-based Online Stochastic Bin Packing
Lagrangian-based Online Stochastic Bin Packing
复制标题
基于拉格朗日的在线随机装箱
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Radovanovic
中科院分区：
文献类型：
--
作者：
Varun Gupta;A. Radovanovic
出于在云中的物理服务器上包装虚拟机的问题，我们研究了两种设置下的在线随机装箱问题-包装与永久项目，包装下的项目离开。在永久项目的设置中，我们提出了第一个真正的分布无关的装箱启发式算法，与所有分布的OPT相比，该算法实现了O（n）的遗憾。我们的算法基本上是梯度下降适当定义的拉格朗日松弛装箱线性规划。我们还证明了我们的启发式对非独立同分布的保证。使用随机延迟的李雅普诺夫函数来平滑输入。对于物品最终离开的设置，我们感兴趣的是最小化稳定状态的箱子数量。我们的算法扩展到物品离开的情况。此外，利用拉格朗日方法，我们将我们的算法推广到一个设置，其中一个项目的处理时间根据它被打包的配置而被某个已知的因子膨胀。
Motivated by the problem of packing Virtual Machines on physical servers in the cloud, we study the problem of online stochastic bin packing under two settings -- packing with permanent items, and packing under item departures. In the setting with permanent items, we present the first truly distribution-oblivious bin packing heuristic that achieves O(√n) regret compared to OPT for all distributions. Our algorithm is essentially gradient descent on suitably defined Lagrangian relaxation of the bin packing Linear Program. We also prove guarantees of our heuristic against non i.i.d. input using a randomly delayed Lyapunov function to smoothen the input. For the setting where items eventually depart, we are interested in minimizing the steady-state number of bins. Our algorithm extends as is to the case of item departures. Further, leveraging the Lagrangian approach, we generalize our algorithm to a setting where the processing time of an item is inflated by a certain known factor depending on the configuration it is packed in.