A dense hierarchy of sublinear time approximation schemes for bin packing
Genre
Pre-printDate
2012-05-23Author
Beigel, RFu, B
Permanent link to this record
http://hdl.handle.net/20.500.12613/4220
Metadata
Show full item recordDOI
10.1007/978-3-642-29700-7_16Abstract
The 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 work
Springer Berlin HeidelbergHas part
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)ADA compliance
For Americans with Disabilities Act (ADA) accommodation, including help with reading this content, please contact scholarshare@temple.eduae974a485f413a2113503eed53cd6c53
http://dx.doi.org/10.34944/dspace/4202