An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem II: Geometric Grouping with Residual LP RoundingResearch Paper
One-dimensional bin packing asks for the fewest unit-capacity bins that hold a given list of items with sizes in . Deciding whether two bins suffice is NP-hard (it contains the partition problem), so no polynomial-time algorithm guarantees a ratio below unless P = NP. The natural question is therefore asymptotic: how small can the additive error …