A sublinear-time approximation scheme for bin packing

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/

zbMATH Keywords

bin packingsublinear-time algorithms

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

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