A new enumeration scheme for the knapsack problem
From MaRDI portal
This paper presents a new enumeration scheme to solve the one-dimensional knapsack problem motivated by some observations on number theory, more specifically on the determination of the number of solutions of linear diophantine equations. This new algorithm is pseudopolynomial and its special features provide a reduction in running time and in the computational memory requirements as compared with other exact (dynamic programming) methods.
Recommendations
Cites work
- A Finite Renewal Algorithm for the Knapsack and Turnpike Models
- A Linear Programming Approach to the Cutting Stock Problem—Part II
- Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
- An Algorithm for Large Zero-One Knapsack Problems
- An algorithm for the computation of knapsack functions
- An algorithm for the solution of the 0-1 knapsack problem
- An upper bound for the zero-one knapsack problem and a branch and bound algorithm
- Approximate Algorithms for the 0/1 Knapsack Problem
- Bounds on Multiprocessing Timing Anomalies
- Computational results with a branch-and-bound algorithm for the general knapsack problem
- Computing Partitions with Applications to the Knapsack Problem
- Discrete-variable extremum problems
- Dynamic programming algorithms for the zero-one knapsack problem
- Fast Approximation Algorithms for Knapsack Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Hard Knapsack Problems
- scientific article; zbMATH DE number 3900494 (Why is no real title available?)
- scientific article; zbMATH DE number 3655621 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3092633 (Why is no real title available?)
- Merging and Sorting Applied to the Zero-One Knapsack Problem
- Multistage Cutting Stock Problems of Two and More Dimensions
- Polynomial-Time Aggregation of Integer Programming Problems
- Resolution of the 0–1 knapsack problem: Comparison of methods
- Shortest-Route Methods: 2. Group Knapsacks, Expanded Networks, and Branch-and-Bound
- Technical Note—Computational Viability of a Constraint Aggregation Scheme for Integer Linear Programming Problems
- Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning
- The knapsack problem: A survey
- The Theory and Computation of Knapsack Functions
- Worst-case analysis of greedy algorithms for the subset-sum problem
Cited in
(12)- A relation between the knapsack and group knapsack problems
- On dominated terms in the general knapsack problem
- The one dimensional Compartmentalised Knapsack problem: a case study
- Determining the K-best solutions of knapsack problems
- Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach
- scientific article; zbMATH DE number 4093181 (Why is no real title available?)
- A New Knapsack Solution Approach by Integer Equivalent Aggregation and Consistency Determination
- Checkerboard pattern: proposals for its generation
- A New Algorithm for the Solution of the Knapsack Problem
- Extension of Brickell’S Algorithm for Breaking High Density Knapsacks
- An algorithm for determining the k-best solutions of the one-dimensional knapsack problem
- A new lower bound for the linear knapsack problem with general integer variables
This page was built for publication: A new enumeration scheme for the knapsack problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1095029)
