文件名称：基于内点的在线随机装箱-研究论文
文件大小：777KB
文件格式：PDF
更新时间：2024-06-29 10:59:41
bin packing primal-dual
装箱是一个算法问题，出现在各种应用中，例如剩余库存系统、运输物流和预约安排。 在其最简单的变体中，T 项目的序列（例如，原材料订单，交货包裹）一次显示一个，并且每个项目必须在到达时包装在可用的箱中（例如，剩余的原材料在库存、运输集装箱）。 物品的大小是来自未知分布的 iid 样本，但物品到达时大小是已知的。 目标是最小化非空 bin 的数量（相当于浪费，定义为非空 bin 中未使用的总空间）。 这个问题已经在运筹学和理论计算机科学社区进行了广泛的研究，但所有现有的启发式方法要么依赖于学习分布，要么与仅针对某些分布类别（具有以下特征的分布）的最佳离线算法相比表现出 o(T) 加性次优性。次线性最优预期浪费）。 在本文中，我们提出了一系列算法，它们是第一个用于随机装箱的真正的分布无视算法，并实现了所有项目大小分布的 O(√T) 加性次优性。 我们的算法受到用于凸优化的近似内点算法的启发。 除了对 iid 序列的后悔保证，我们还证明了一般 noni.id 输入序列的一系列新的后悔边界，包括对局部对抗性扰动的 iid 序列的保证。 据我们所知，这些是用于在线随机包装的非 iid 和非随机排列输入序列的第一个这样的结果。