A successive approximation algorithm for the multiple knapsack problem

作者：Wang Zhenbo^*; Xing Wenxun

来源：Journal of Combinatorial Optimization, 2009, 17(4): 347-366.

DOI：10.1007/s10878-007-9116-y

• Multiple knapsack problem
• Approximation algorithm
• Worst-case analysis

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.

• 出版日期2009-5
• 单位清华大学