A sublinear-time approximation scheme for bin packing
A sublinear-time approximation scheme for bin packing
复制标题
DOI：
10.1016/j.tcs.2009.08.006
复制
发表时间：
2009-11
期刊：
影响因子：
--
通讯作者：
Tugkan Batu;P. Berenbrink;C. Sohler
中科院分区：
文献类型：
--
作者：
Tugkan Batu;P. Berenbrink;C. Sohler
装箱问题定义如下：给定一组n个大小为0<；w1，w2，…的物品，Wn≤1，找到将这些物品包装到可能的最小数量的单位大小的垃圾箱中的方法。我们给出了装箱问题的一个次线性时间渐近逼近方案，即对于任何ϵ>；0，我们提出了一个算法Aϵ，它可以对输入实例进行抽样访问，并输出一个值k，使得Copt≤k≤(1+ϵ)⋅Copt+1，其中Copis是最优解的代价)。显然，均匀采样本身不允许在此设置中使用次线性时间算法；少数项目可能构成总权重的大部分，并且均匀样本不会命中它们。在这项工作中，我们使用加权样本，其中项目i的抽样概率与其权重成正比：即概率wi/∑iwi。在加权样本存在的情况下，近似算法的运行时间为Õ(n⋅Poly(1/ϵ))+g(1/ϵ)时间，其中g(X)是x的指数函数，当同时允许加权采样和均匀采样时，Õ(n1/3⋅Poly(1/ϵ))+g(1/ϵ)时间满足要求。除了COPT的近似值外，我们的算法还可以输出一个固定大小的布局“模板”，该模板稍后可以用来在线性时间内找到接近最优的布局。
The bin packing problem is defined as follows: given a set of n items with sizes 0<w1,w2,…,wn≤1, find a packing of these items into a minimum number of unit-size bins possible. We present a sublinear-time asymptotic approximation scheme for the bin packing problem; that is, for any ϵ>0, we present an algorithm Aϵthat has sampling access to the input instance and outputs a value k such that Copt≤k≤(1+ϵ)⋅Copt+1, where Coptis the cost of an optimal solution. It is clear that uniform sampling by itself will not allow a sublinear-time algorithm in this setting; a small number of items might constitute most of the total weight and uniform samples will not hit them. In this work we use weighted samples, where item i is sampled with probability proportional to its weight: that is, with probability wi/∑iwi. In the presence of weighted samples, the approximation algorithm runs in Õ(n⋅poly(1/ϵ))+g(1/ϵ) time, where g(x) is an exponential function of x. When both weighted sampling and uniform sampling are allowed, Õ(n1/3⋅poly(1/ϵ))+g(1/ϵ) time suffices. In addition to an approximate value to Copt, our algorithm can also output a constant-size “template” of a packing that can later be used to find a near-optimal packing in linear time.