A new enumeration scheme for the knapsack problem

DOI10.1016/0166-218X(87)90024-2zbMath0631.90044WikidataQ127719690 ScholiaQ127719690MaRDI QIDQ1095029

Horacio Hideki Yanasse, Nei Yoshihiro Soma

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

enumerationlinear diophantine equationsone-dimensional knapsack problempseudopolynomial

Mathematics Subject Classification ID

Integer programming (90C10) Linear Diophantine equations (11D04)

Related Items (8)

The one dimensional Compartmentalised Knapsack problem: a case study ⋮ A new lower bound for the linear knapsack problem with general integer variables ⋮ Determining the \(K\)-best solutions of knapsack problems ⋮ On dominated terms in the general knapsack problem ⋮ Solving Medium-Density Subset Sum Problems in Expected Polynomial Time: An Enumeration Approach ⋮ Checkerboard pattern: proposals for its generation ⋮ An algorithm for determining the K-best solutions of the one-dimensional Knapsack problem ⋮ A relation between the knapsack and group knapsack problems

Uses Software

• Algorithm 37

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Dynamic programming algorithms for the zero-one knapsack problem
• 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
• Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
• An algorithm for the computation of knapsack functions
• Technical Note—Computational Viability of a Constraint Aggregation Scheme for Integer Linear Programming Problems
• Worst-case analysis of greedy algorithms for the subset-sum problem
• Polynomial-Time Aggregation of Integer Programming Problems
• Fast Approximation Algorithms for Knapsack Problems
• Hard Knapsack Problems
• An Algorithm for Large Zero-One Knapsack Problems
• The knapsack problem: A survey
• Resolution of the 0–1 knapsack problem: Comparison of methods
• Merging and Sorting Applied to the Zero-One Knapsack Problem
• Computing Partitions with Applications to the Knapsack Problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Approximate Algorithms for the 0/1 Knapsack Problem
• Computational results with a branch-and-bound algorithm for the general knapsack problem
• Shortest-Route Methods: 2. Group Knapsacks, Expanded Networks, and Branch-and-Bound
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• Multistage Cutting Stock Problems of Two and More Dimensions
• Discrete-Variable Extremum Problems
• A Finite Renewal Algorithm for the Knapsack and Turnpike Models
• The Theory and Computation of Knapsack Functions
• Bounds on Multiprocessing Timing Anomalies
• Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning

This page was built for publication: A new enumeration scheme for the knapsack problem