An asymptotically exact algorithm for the high-multiplicity bin packing problem

• 成果类型: Article
• 署名作者: Filippi, C; Agnetis, A
• 署名单位: University of Padua; University of Siena
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-004-0567-y
• 发表日期: 2005
• 页码: 21-37
• 关键词: Optimization

摘要

The bin packing problem consists of finding the minimum number of bins, of given capacity D, required to pack a set of objects, each having a certain weight. We consider the high-multiplicity version of the problem, in which there are only C different weight values. We show that when C=2 the problem can be solved in time O( log D). For the general case, we give an algorithm which provides a solution requiring at most C-2 bins more than the optimal solution, i.e., an algorithm that is asymptotically exact. For fixed C, the complexity of the algorithm is O(poly( log D)), where poly(center dot) is a polynomial function not depending on C.