论文标题
在线矢量箱包装的真正渐近下限
Truly asymptotic lower bounds for online vector bin packing
论文作者
论文摘要
在这项工作中，我们考虑在线矢量箱包装。众所周知，在绝对含义上，没有算法可以具有$ O（d/\ log^2 d）$的竞争比率，尽管该问题的上限始终以渐近意义显示。由于传统上研究了垃圾箱堆积的变体，并且由于两种措施不同，因此我们将重点放在渐近度量上，并在渐近竞争比率上证明了新的下限。在这项工作之前的现有下限远小于$ 3 $，即使对于非常大的尺寸。 对于每个这样的维度$ d $，我们大大提高了渐近竞争比率上最著名的下限（作为绝对竞争比率的副产品，在绝对竞争比率上是副产品）。为了获得这些结果，我们使用几种不同的构造，其中一种是一种自适应结构，显示了$ω（\ sqrt {d}）$的下限。我们的主要结果是，在渐近意义上，竞争比的$ω（d/\ log^2 d）$的下限也具有。最后的结果需要仔细改编在线着色的结构，而不是简单的黑盒降低。
In this work, we consider online vector bin packing. It is known that no algorithm can have a competitive ratio of $o(d/\log^2 d)$ in the absolute sense, though upper bounds for this problem were always shown in the asymptotic sense. Since variants of bin packing are traditionally studied with respect to the asymptotic measure and since the two measures are different, we focus on the asymptotic measure and prove new lower bounds on the asymptotic competitive ratio. The existing lower bounds prior to this work were much smaller than $3$ even for very large dimensions. We significantly improve the best known lower bounds on the asymptotic competitive ratio (and as a byproduct, on the absolute competitive ratio) for online vector packing of vectors with $d \geq 3$ dimensions, for every such dimension $d$. To obtain these results, we use several different constructions, one of which is an adaptive construction showing a lower bound of $Ω(\sqrt{d})$. Our main result is that the lower bound of $Ω(d/\log^2 d)$ on the competitive ratio holds also in the asymptotic sense. The last result requires a careful adaptation of constructions for online coloring rather than simple black-box reductions.
