论文标题
在线矢量箱包装的渐近下限
An Asymptotic Lower Bound for Online Vector Bin Packing
论文作者
论文摘要
我们考虑在线矢量箱包装问题，其中$ d $二维向量指定的$ n $项目必须以最少的相同$ d $维垃圾箱的数量包装。 Azar等。 （Stoc'13）表明，对于任何在线算法$ a $，存在I实例i，因此$ a（i）$，$ a $ a $ to to pack $ i $的垃圾箱数为$ω（d/\ log^2 d）$ times $ times $ opt（i）$，最小的箱子to pack to pack to pack $ i $ i $。但是，在这些情况下，$ opt（i）$仅为$ o（\ log d）$，当$ opt（i）\ gg d $ $渐近竞争比率上，它打开了改进算法的可能性。我们通过证明任何任意函数$ q（\ cdot）$和任何随机在线算法$ a $ a $来排除这一点，存在实例$ i $，以便$ e [a（i）] \ geq c \ geq c \ cdot d/\ log^3d \ cdot opt（i） + q（i） + q（i） + q（i） + q（d）$，对于某些通用常数$ c $。
We consider the online vector bin packing problem where $n$ items specified by $d$-dimensional vectors must be packed in the fewest number of identical $d$-dimensional bins. Azar et al. (STOC'13) showed that for any online algorithm $A$, there exist instances I, such that $A(I)$, the number of bins used by $A$ to pack $I$, is $Ω(d/\log^2 d)$ times $OPT(I)$, the minimal number of bins to pack $I$. However in those instances, $OPT(I)$ was only $O(\log d)$, which left open the possibility of improved algorithms with better asymptotic competitive ratio when $OPT(I) \gg d$. We rule this out by showing that for any arbitrary function $q(\cdot)$ and any randomized online algorithm $A$, there exist instances $I$ such that $ E[A(I)] \geq c\cdot d/\log^3d \cdot OPT(I) + q(d)$, for some universal constant $c$.
