论文标题
通过迭代随机舍入改善了向量箱堆积的近似值
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding
论文作者
论文摘要
我们研究了$ d $二维矢量箱包装（$ d $ vbp）问题，这是对资源分配和调度中心应用程序的垃圾箱包装的概括。在$ d $ vbp中，我们得到了一组项目，每个项目的特征是$ d $维数量矢量；目的是将项目划分为最少数量的子集（垃圾箱），以使每个子集中的项目总数最多为每个维度的$ 1 $。 我们的主要结果是用于$ d $ vbp的渐近近似算法，可为所有$ d \ in \ mathbb {n} $和任何$ \ varepsilon> 0 $;在这里，$χ（d）$是严格的积极功能。由于Bansal，Caprara和Sviridenko（Sicomp 2010），对于任何$ d> 3 $，这会改善$ \ left（1+ \ ln D + \ Varepsilon \ right）$的最著名的渐近比（1+ \ ln d + \ varepsilon \ right）。通过稍微修改我们的算法以包括初始匹配阶段并应用更严格的分析，我们获得了$ \ left的渐近近似值（\ frac {4} {3} {3} {3}+\ varepsilon \ right）$用于$ d = 2 $的特殊情况，从而实质上改善$ \ left（\ frac {3} {2}+\ varepsilon \ right）$由于Bansal，Elias和Khan（Soda 2016）。 我们的算法迭代求解了剩余实例（来自以前的迭代）的配置LP松弛，并根据配置LP的解决方案进行了少量配置。虽然Karmarkar和Karp（Focs 1982）已经使用了迭代舍入来建立其著名的经典（一维）垃圾箱包装结果，但在（矢量）垃圾箱包装的背景下，这里首次使用迭代的随机舍入。我们的结果表明，迭代随机舍入是一种近似$ d $ vbp的功能强大的工具，从而导致简单的算法具有改进的近似保证。
We study the $d$-dimensional Vector Bin Packing ($d$VBP) problem, a generalization of Bin Packing with central applications in resource allocation and scheduling. In $d$VBP, we are given a set of items, each of which is characterized by a $d$-dimensional volume vector; the objective is to partition the items into a minimum number of subsets (bins), such that the total volume of items in each subset is at most $1$ in each dimension. Our main result is an asymptotic approximation algorithm for $d$VBP that yields a ratio of $(1+\ln d-χ(d) +\varepsilon)$ for all $d \in \mathbb{N}$ and any $\varepsilon > 0$; here, $χ(d)$ is some strictly positive function. This improves upon the best known asymptotic ratio of $ \left(1+ \ln d +\varepsilon\right)$ due to Bansal, Caprara and Sviridenko (SICOMP 2010) for any $d >3$. By slightly modifying our algorithm to include an initial matching phase and applying a tighter analysis we obtain an asymptotic approximation ratio of $\left(\frac{4}{3}+\varepsilon\right)$ for the special case of $d=2$, thus substantially improving the previous best ratio of $\left(\frac{3}{2}+\varepsilon\right)$ due to Bansal, Elias and Khan (SODA 2016). Our algorithm iteratively solves a configuration LP relaxation for the residual instance (from previous iterations) and samples a small number of configurations based on the solution for the configuration LP. While iterative rounding was already used by Karmarkar and Karp (FOCS 1982) to establish their celebrated result for classic (one-dimensional) Bin Packing, iterative randomized rounding is used here for the first time in the context of (Vector) Bin Packing. Our results show that iterative randomized rounding is a powerful tool for approximating $d$VBP, leading to simple algorithms with improved approximation guarantees.
