A dense hierarchy of sublinear time approximation schemes for bin packing

DOI10.1007/978-3-642-29700-7_16zbMATH Open1304.68208arXiv1007.1260OpenAlexW2107214893MaRDI QIDQ2897992FDOQ2897992

Richard Beigel, Bin Fu

Publication date: 16 July 2012

Published in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (Search for Journal in Brave)

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,\mathrm{...},a_n$ in $(0,1]$. Using uniform sampling, which selects a random element from the input list each time, we develop a randomized $O(n(logn)(loglogn)oversu{m}_{i=1}^n{a}_i+(1overepsilon{)}^{O(1overepsilon)})$ time $(1+epsilon)$-approximation scheme for the bin packing problem. We show that every randomized algorithm with uniform random sampling needs $Omega(noversu{m}_{i=1}^n{a}_i)$ time to give an $(1+epsilon)$-approximation. For each function $s(n):NightarrowN$, define $sum(s(n))$ to be the set of all bin packing problems with the sum of item sizes equal to $s(n)$. For a constant $bin(0,1)$, every problem in $sum(n^b)$ has an $O(n^{1-b}(logn)(loglogn)+(1overepsilon{)}^{O(1overepsilon)})$ time $(1+epsilon)$-approximation for an arbitrary constant $epsilon$. On the other hand, there is no $o(n^{1-b})$ time $(1+epsilon)$-approximation scheme for the bin packing problems in $sum(n^b)$ for some constant $epsilon>0$.

Full work available at URL: https://arxiv.org/abs/1007.1260

Recommendations

• A sublinear-time approximation scheme for bin packing
• An Efficient Approximation Scheme for Variable-Sized Bin Packing
• \(O((\log n)^{2})\) time online approximation schemes for bin packing and subset sum problems
• On a dual version of the one-dimensional bin packing problem
• Linear time-approximation algorithms for bin packing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Cited In (12)

• Denser packings obtained in \(O(n \log \log n)\) time
• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• Partially dynamic bin packing can be solved within \(1 + \varepsilon\) in (amortized) polylogarithmic time
• Streaming algorithms for bin packing and vector scheduling
• Linear time-approximation algorithms for bin packing
• Tight approximation algorithms for geometric bin packing with skewed items
• Tight Approximation Algorithms For Geometric Bin Packing with Skewed Items
• Fast approximate PCPs for multidimensional bin-packing problems
• Sublinear Time Width-Bounded Separators and Their Application to the Protein Side-Chain Packing Problem
• Comments on the hierarchically structured bin packing problem
• Bridging gap between standard and differential polynomial approximation: The case of bin-packing
• Approximation algorithms for a hierarchically structured bin packing problem

This page was built for publication: A dense hierarchy of sublinear time approximation schemes for bin packing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2897992)