A sublinear-time approximation scheme for bin packing
From MaRDI portal
Publication:1034628
DOI10.1016/j.tcs.2009.08.006zbMath1194.68254OpenAlexW2046102647MaRDI QIDQ1034628
Petra Berenbrink, Christian Sohler, Tuğkan Batu
Publication date: 6 November 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://eprints.lse.ac.uk/25979/
Related Items (2)
Sublinear-time algorithms for counting star subgraphs via edge sampling ⋮ Streaming algorithms for bin packing and vector scheduling
Cites Work
- Unnamed Item
- Unnamed Item
- Optimal time bounds for approximate clustering
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Bin packing can be solved within 1+epsilon in linear time
- Sublinear time algorithms for metric space problems
- Property testing and its connection to learning and approximation
- On the sum-of-squares algorithm for bin packing
- A Linear Programming Approach to the Cutting-Stock Problem
- Sublinear‐time approximation algorithms for clustering via random sampling
- On sums of independent random variables with unbounded variance, and estimating the average degree in a graph
- Estimating the weight of metric minimum spanning trees in sublinear-time
- Approximating Average Parameters of Graphs
- Quick k-Median, k-Center, and Facility Location for Sparse Graphs
- A Linear Programming Approach to the Cutting Stock Problem—Part II
- Estimating Sum by Weighted Sampling
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- The Complexity of Approximating the Entropy
- Automata, Languages and Programming
- Property testing in bounded degree graphs
This page was built for publication: A sublinear-time approximation scheme for bin packing
