A successive approximation algorithm for the multiple knapsack problem (Q1029265)

This paper considers such an approximation algorithm that packs \(m\) knapsacks in nondecreasing order of their capacities: \(c_1\leq\cdots\leq c_m\). If \(H\) is an exact algorithm for the one-knapsack problem, the successive algorithm \(H^m\) has the following tight approximation guarantees: for \(m= 2\): \(2/3\) if \(c_1< c_2\), and \(3/4\): if \(c_1= c_2\), for \(m= 3\): \(3/4\) if \(c_1= c_2= c_3\), and \(5/7\); \(2/3\); \(3/4\); \(7/10\) and \(8/11\) respectively, depending on the ratios of the capacities. For \(m> 3\) the problem of determining tight error bounds for \(H^m\) remains open. If \(H'\) is an (2-epsilon)-approximation algorithm for the one-knapsack problem, the error bounds carry over for \(H^{\prime m}\) by the factor (1-epsilon).