论文标题
用于在线多个背包的最佳算法
An Optimal Algorithm for Online Multiple Knapsack
论文作者
论文摘要
在在线多重背包问题中，算法面对一系列项目，并且必须在$ n $ bin（knapsacks）中拒绝或不可撤销地存储每个项目。一个算法的增益等于所接受项目的大小的总和，目标是最大化总增益。 到目前为止，对于这个自然问题，最好的解决方案是$ 0.5 $竞争算法的首先拟合（结果适用于任何$ n \ geq 2 $）。我们提出了第一个超过此比率的算法，达到了$ 1/（1+ \ ln（2））-o（1/n）\约0.5906 -O（1/n）$。我们的算法是确定性的，最佳的较低级术语，因为Cygan等人先前给出了随机溶液的$ 1/（1+ \ ln（2））$的上限。 [TOCS 2016]。此外，我们表明，通过将其上限提高到$ 1/（1+ \ ln（2）） - o（1/n）$，低阶项是确定性算法不可避免的。
In the online multiple knapsack problem, an algorithm faces a stream of items, and each item has to be either rejected or stored irrevocably in one of $n$ bins (knapsacks) of equal size. The gain of an~algorithm is equal to the sum of sizes of accepted items and the goal is to maximize the total gain. So far, for this natural problem, the best solution was the $0.5$-competitive algorithm First Fit (the result holds for any $n \geq 2$). We present the first algorithm that beats this ratio, achieving the competitive ratio of $1/(1+\ln(2))-O(1/n) \approx 0.5906 - O(1/n)$. Our algorithm is deterministic and optimal up to lower-order terms, as the upper bound of $1/(1+\ln(2))$ for randomized solutions was given previously by Cygan et al. [TOCS 2016]. Furthermore, we show that the lower-order term is inevitable for deterministic algorithms, by improving their upper bound to $1/(1+\ln(2))-O(1/n)$.
