A dense hierarchy of sublinear time approximation schemes for bin packing
Permanent link to this recordhttp://hdl.handle.net/20.500.12613/4220
MetadataShow full item record
AbstractThe bin packing problem is to find the minimum number of bins of size one to pack a list of items with sizes a 1,..., a n in (0,1]. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized (Formula Presented) time (1 + ε)- approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs (Formula Presented) time to give an (1 + ε)-approximation. For each function s(n): N → N, define Σ(s(n)) to be the set of all bin packing problems with the sum of item sizes equal to s(n). We show that Σ(n b) is NP-hard for every b ∈ (0,1]. 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 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. © 2012 Springer-Verlag.
Citation to related workSpringer Berlin Heidelberg
Has partLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ADA complianceFor Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact email@example.com