A robust APTAS for the classical bin packing problem

• 成果类型: Article; Proceedings Paper
• 署名作者: Epstein, Leah; Levin, Asaf
• 署名单位: Hebrew University of Jerusalem; University of Haifa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-007-0200-y
• 发表日期: 2009
• 页码: 33-49
• 关键词: algorithms; time

摘要

Bin packing is a well studied problem which has many applications. In this paper we design a robust APTAS for the problem. The robust APTAS receives a single input item to be added to the packing at each step. It maintains an approximate solution throughout this process, by slightly adjusting the solution for each new item. At each step, the total size of items which may migrate between bins must be bounded by a constant factor times the size of the new item. We show that such a property cannot be maintained with respect to optimal solutions.