Additive Gap for Bin Packing with Three Items per BinResearch Paper
In bin packing, items with sizes in must be partitioned into bins of total size at most one, using as few bins as possible; is that minimum. The problem is strongly NP-hard even in the 3-partition regime, where every size lies in and a bin holds at most three items, so research has concentrated on additive guarantees …