A successive approximation algorithm for the multiple knapsack problem |
| |
Authors: | Zhenbo Wang Wenxun Xing |
| |
Institution: | (1) Department of Mathematical Sciences, Tsinghua University, Beijing, 100084, China |
| |
Abstract: | 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. |
| |
Keywords: | Multiple knapsack problem Approximation algorithm Worst-case analysis |
本文献已被 SpringerLink 等数据库收录! |
|