Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
A stochastic online version of the classical bin packing problem, where a bin corresponds to the capacity of a resource allocated among streams of requests at discrete time units, is a fundamental problem that arises in a wide variety of application areas including bandwidth allocation in networks, memory management in computers, and message transmission in slotted network channels. We derive a mathematical analysis of the corresponding multi-dimensional stochastic process, potentially infinite in each dimension, under a general class of scheduling policies based on a combination of a Lyapunov function technique and matrix-analytic methods. Our analysis yields stability conditions and stationary distributions for this stochastic bin packing process under general probability distributions. We further provide some algorithmic techniques for the numerical computation of these measures. Copyright ©Taylor & Francis, Inc.
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Igor Devetak, Andreas Winter
ISIT 2003
Robert F. Gordon, Edward A. MacNair, et al.
WSC 1985
David Cash, Dennis Hofheinz, et al.
Journal of Cryptology