文章基本信息

标题：A Dense Hierarchy of Sublinear Time Approximation Schemes for Bin Packing
本地全文：下载
作者：Richard Beigel, Bin Fu
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a1an in (01] . Using uniform sampling, which selects a random element from the input list each time, we develop a randomized O(ni=1ain(logn)(loglogn)+(1)O(1)) time (1+)-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs (nni=1ai) time to give an (1+)-approximation. For each function s(n):NN, define (s(n)) to be the set of all bin packing problems with the sum of item sizes equal to s(n). For a constant b(01) , every problem in (nb) has an O(n1−b(logn)(loglogn)+(1)O(1)) time (1+)-approximation for an arbitrary constant . On the other hand, there is no o(n1−b) time (1+)-approximation scheme for the bin packing problems in (nb) for some constant 0. We show that (nb) is NP-hard for every b(01] . This implies a dense sublinear time hierarchy of approximation schemes for a class of NP-hard problems, which are derived from the bin packing problem. We also show a randomized streaming approximation scheme for the bin packing problem such that it needs only constant updating time and constant space, and outputs an (1+)-approximation in (1)O(1) time. Let S()-bin packing be the class of bin packing problems with each input item of size at least . This research also gives a natural example of NP-hard problem (S()-bin packing) that has a constant time approximation scheme, and a constant time and space sliding window streaming approximation scheme, where is a positive constant.
关键词：Approximation, bin packing, hierarchy, Sublinear time