In the online bin packing problem, a sequence of items is revealed one at a time, and each item must be packed into an available bin instantly upon its arrival. In this paper, we revisit the problem under a setting where the total number of items T is known in advance, also known as the closed online bin packing problem. Specifically, we study both the stochastic model and the random permutation model. We develop and analyze an adaptive algorithm that solves an offline bin packing problem at geometric time intervals and uses the offline optimal solution to guide online packing decisions. Under both models, we show that the algorithm achieves C\sqrt{T} regret (in terms of the number of used bins) compared to the hindsight optimal solution, where C is a universal constant (<= 13) that bears no dependence on the underlying distribution or the item sizes. The result shows the lower bound barrier of \Omega(\sqrt{T \log T}) in Shor (1986) can be broken with solely the knowledge of the horizon T, but without a need of knowing the underlying distribution. As to the algorithm analysis, we develop a new approach to analyzing the packing dynamic using the notion of exchangeable random variables. The approach creates a symmetrization between the offline solution and the online solution, and it is used to analyze both the algorithm performance and various benchmarks related to the bin packing problem. For the latter one, our analysis provides an alternative (probably simpler) treatment and tightens the analysis of the asymptotic benchmark of the stochastic bin packing problem in Rhee and Talagrand (1989a,b). As the analysis only relies on a symmetry between the offline and online problems, the algorithm and benchmark analyses can be naturally extended from the stochastic model to the random permutation model.
翻译:在在线垃圾包装问题中, 一次一次显示一个项目序列, 每个项目必须在到达时立即被打包到可用的垃圾桶中。 在本文中, 我们在一个设置下重新审视问题, T项的总数是事先知道的, 也就是封闭的在线垃圾包装问题。 具体地说, 我们既研究随机分析模型, 也研究随机调整模型。 我们开发并分析一个适应性算法, 在几何时间间隔解决离线包装问题, 并使用离线最佳解决方案来指导在线包装决定。 在两种模型中, 我们显示算法在使用 C\ sqrart{T} 之后, 我们发现, 算法实现了 C\ sqright 的简化处理基准, 与后见的最佳解决方案相比, 我们重现的计算法分析( \\ 13) ) 是一个通用常态常态的常态( 13) 。 结果显示 \ Omega (\ sqrort{T\log T} ) 的下界屏障障碍只能从对地平面 T 进行解算法和离线分析, 但是, 我们不需要了解基础的分布。 。 对于算法分析, 我们的轨法分析是用来分析, 和内部的解算法分析, 的解算法分析,, 。