论文标题
用于在线堆叠的渐近最佳算法
An Asymptotically Optimal Algorithm for Online Stacking
论文作者
论文摘要
考虑一个存储区域，将到达物品临时存储在有限的容量堆栈中，直到出发为止。我们研究了决定将到达物品放在哪里的问题，目的是最大程度地减少随着时间的推移使用的最大堆栈数量。必须在物品到达后立即做出决定，我们假设我们只有有关到达物品的出发时间以及当前在存储区域的项目的信息。如果下面的物品在以后出发时，我们只允许将项目放在另一个项目的顶部。我们将此问题称为在线堆叠。我们假设选择了存储时间间隔。从$ [0，1] \ times [0，1] $使用具有有界概率密度函数的未知分布。在这种温和的情况下，我们提出了一个简单的多项式在线算法，并表明竞争比率为$ 1 $的概率。结果如果堆栈容量为$ o（\ sqrt {n}）$，则结果保持，其中$ n $是项目数，包括容量为常数的现实情况。我们的实验表明，我们的结果也具有实际相关性。据我们所知，我们是第一个提出用于在线堆叠的渐近最佳算法的人，这是计算物流中许多现实世界应用的重要问题。
Consider a storage area where arriving items are stored temporarily in bounded capacity stacks until their departure. We look into the problem of deciding where to put an arriving item with the objective of minimizing the maximum number of stacks used over time. The decision has to be made as soon as an item arrives, and we assume that we only have information on the departure times for the arriving item and the items currently at the storage area. We are only allowed to put an item on top of another item if the item below departs at a later time. We refer to this problem as online stacking. We assume that the storage time intervals are picked i.i.d. from $[0, 1] \times [0, 1]$ using an unknown distribution with a bounded probability density function. Under this mild condition, we present a simple polynomial time online algorithm and show that the competitive ratio converges to $1$ in probability. The result holds if the stack capacity is $o(\sqrt{n})$, where $n$ is the number of items, including the realistic case where the capacity is a constant. Our experiments show that our results also have practical relevance. To the best of our knowledge, we are the first to present an asymptotically optimal algorithm for online stacking, which is an important problem with many real-world applications within computational logistics.
