This item is non-discoverable
Loading...
Non-discoverable
A dense hierarchy of sublinear time approximation schemes for bin packing
Beigel, R Fu, B
Beigel, R
Fu, B
Citations
Altmetric:
Genre
Pre-print
Date
2012-05-23
Advisor
Committee member
Group
Department
Permanent link to this record
Collections
Research Projects
Organizational Units
Journal Issue
DOI
10.1007/978-3-642-29700-7_16
Abstract
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.
Description
Citation
Citation to related work
Springer Berlin Heidelberg
Has 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.edu