Packing Small Vectors
Packing Small Vectors
复制标题
DOI：
10.1137/1.9781611974331.ch103
复制
发表时间：
2016-01
期刊：
影响因子：
--
通讯作者：
Y. Azar;I. Cohen;A. Fiat;A. Roytman
中科院分区：
文献类型：
--
作者：
Y. Azar;I. Cohen;A. Fiat;A. Roytman
在线d维向量打包建模了许多设置，例如在作业具有多种资源需求（CPU、内存等）的数据中心中最小化资源。然而，没有一种在线d维向量填充算法可以达到比d更好的竞争比。幸运的是，在许多自然应用中，向量相对较小，因此下界不成立。对于足够小的向量，已知一个O（log d）竞争算法。我们将其改进为一个恒定的竞争比，任意接近于2.718，假设向量足够小。我们给出了二维情况下的改进结果。对于任意小的向量，二维向量填充的First Fit算法并不优于2-competitive算法。我们提出了一个自然的First Fit变量族，对于足够小的向量，优化参数的竞争比为1.48。我们改进了1.48的竞争比（不是通过First Fit变体），并给出了一个任意接近4/3的竞争比，用于包装小的二维向量。我们表明，对于二维向量，没有任何算法可以达到比4/3更好的竞争比，即使一个算法允许在任意多个箱子中分割向量。
Online d-dimensional vector packing models many settings such as minimizing resources in data centers where jobs have multiple resource requirements (CPU, Memory, etc.). However, no online d-dimensional vector packing algorithm can achieve a competitive ratio better than d. Fortunately, in many natural applications, vectors are relatively small, and thus the lower bound does not hold. For sufficiently small vectors, an O(log d)-competitive algorithm was known. We improve this to a constant competitive ratio, arbitrarily close to e a 2.718, given that vectors are sufficiently small. We give improved results for the two dimensional case. For arbitrarily small vectors, the First Fit algorithm for two dimensional vector packing is no better than 2-competitive. We present a natural family of First Fit variants, and for optimized parameters get a competitive ratio a 1.48 for sufficiently small vectors. We improve upon the 1.48 competitive ratio -- not via a First Fit variant -- and give a competitive ratio arbitrarily close to 4/3 for packing small, two dimensional vectors. We show that no algorithm can achieve better than a 4/3 competitive ratio for two dimensional vectors, even if one allows the algorithm to split vectors among arbitrarily many bins.