A successive approximation algorithm for the multiple knapsack problem
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).
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- scientific article; zbMATH DE number 1418266
- Parameterized approximation scheme for the multiple knapsack problem
- Parameterized approximation scheme for the multiple knapsack problem
- Approximation for multi-knapsack problem
- Approximation algorithms for the multiple knapsack problem with assignment restrictions
- Approximation for knapsack problems with multiple constraints
- An exact algorithm for large multiple knapsack problems
- Approximability of two variants of multiple knapsack problems
- A 3/4-approximation algorithm for multiple subset sum
- A bound and bound algorithm for the zero-one multiple knapsack problem
- A new fully polynomial time approximation scheme for the Knapsack problem
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- A PTAS for the multiple subset sum problem with different knapsack capacities
- An Efficient Algorithm for the 0-1 Knapsack Problem
- An exact algorithm for large multiple knapsack problems
- An upper bound for the zero-one knapsack problem and a branch and bound algorithm
- Computing Partitions with Applications to the Knapsack Problem
- Fast Approximation Algorithms for Knapsack Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1302173 (Why is no real title available?)
- scientific article; zbMATH DE number 2107164 (Why is no real title available?)
- New trends in exact algorithms for the \(0-1\) knapsack problem
- The multiple subset sum problem
- Worst-case analysis of the subset sum algorithm for bin packing.
- Knapsack with variable weights satisfying linear constraints
- Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
- Two-group knapsack game
- Worst-case performance of the successive approximation algorithm for four identical knapsacks
- A Fast Approximation Scheme for the Multiple Knapsack Problem
- An approximate binary search algorithm for the multiple-choice knapsack problem
- A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
- A Branch-and-Price Algorithm for the Multiple Knapsack Problem
- An addendum to: ``Some thoughts on the 2-approximation algorithm for knapsack problems: a survey
This page was built for publication: A successive approximation algorithm for the multiple knapsack problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029265)
