Fully dynamic bin packing revisited
Fully dynamic bin packing revisited
复制标题
DOI：
10.1007/s10107-018-1325-x
复制
发表时间：
2014-11
影响因子：
2.7
通讯作者：
Sebastian Berndt;K. Jansen;Kim-Manuel Klein
中科院分区：
文献类型：
--
作者：
Sebastian Berndt;K. Jansen;Kim-Manuel Klein
我们考虑了完全动态的装箱问题，其中物品以在线方式到达和离开，并且允许重新包装先前包装的物品。当然，我们的目标是最大限度地减少使用的垃圾箱数量和重新包装的数量。最近引入的一种方法来衡量重新包装成本在每一个时间步是themigration因素，定义为总规模的重新包装项目除以大小的到达或离开的项目。关于箱数和迁移因子之间的权衡，如果我们希望实现箱数的渐近竞争比，一个相对简单的论证证明了迁移因子的下界。我们建立了一个几乎匹配的上限，使用一个新的动态舍入技术和新的想法来处理小项目在一个动态的设置，这样就不需要摊销。我们的算法的运行时间是多项式的项目数snandin。以前的最佳权衡是一个渐进的竞争比为箱（而不是），需要一个摊销的重新包装的数量（而在我们的计划重新包装的数量是独立的非摊销）。
We consider thefully dynamic bin packingproblem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. A recently introduced way of measuring the repacking costs at each timestep is themigration factor,defined as the total size of repacked items divided by the size of an arriving or departing item. Concerning the trade-off between number of bins and migration factor, if we wish to achieve an asymptotic competitive ratio offor the number of bins, a relatively simple argument proves a lower bound offor the migration factor. We establish a nearly matching upper bound ofusing a new dynamic rounding technique and new ideas to handle small items in a dynamic setting such that no amortization is needed. The running time of our algorithm is polynomial in the number of itemsnandin. The previous best trade-off was for an asymptotic competitive ratio offor the bins (rather than) and needed an amortized number ofrepackings (while in our scheme the number of repackings is independent ofnand non-amortized).