Better approximation algorithms for bin covering

摘要: Bin covering takes as input a list of items with sizes in (0, 1) and places them into bins unit demand so to maximize the number whose is satisfied. This sense dual problem classical one-dimensional bin packing problem, but has for many years lagged behind latter terms quality best approximation algorithms. We design algorithms this that close gap, both worst- average-case results. present (1) first asymptotic scheme offline version, (2) have bounded worst-case behavior instances discrete item expected asymptotically optimal all “perfect-packing distributions” (ones which packings sublinear waste), (3) learning algorithm distributions. The are based on recently-developed online Sum-of-Squares packing. also experimental analysis comparing suggesting one them, Sum-of-Squares-with-Threshold algorithm, performs quite well even distributions do not perfect-packing property.