论文标题
有关有序的开放式垃圾箱包装的更多信息
More on ordered open end bin packing
论文作者
论文摘要
我们考虑有序的开放式垃圾箱包装问题。 $（0,1] $的尺寸项目逐一呈现，以此顺序分配给垃圾箱。可以将一个物品分配给当前总尺寸严格低于$ 1 $的任何垃圾箱。这也意味着箱子还可以超过其最后一个包装的物品。我们在在线竞争的比例很严格。低于$ 2 $，它与最佳的绝对近似值相比，这与$ 2 $相比，我们还研究了脱机问题，而项目的序列仍在序列中。
We consider the Ordered Open End Bin Packing problem. Items of sizes in $(0,1]$ are presented one by one, to be assigned to bins in this order. An item can be assigned to any bin for which the current total size strictly below $1$. This means also that the bin can be overloaded by its last packed item. We improve lower and upper bounds on the asymptotic competitive ratio in the online case. Specifically, we design the first algorithm whose asymptotic competitive ratio is strictly below $2$ and it is close to the lower bound. This is in contrast to the best possible absolute approximation ratio, which is equal to $2$. We also study the offline problem where the sequence of items is known in advance, while items are still assigned to bins based on their order in the sequence. For this scenario we design an asymptotic polynomial time approximation scheme.
