A new enumeration scheme for the knapsack problem
type: Item
instance of: scholarly article
title: A new enumeration scheme for the knapsack problem
zbMATH Open document ID: 0631.90044
DOI: 10.1016/0166-218X(87)90024-2
author: Horacio Hideki Yanasse
author: Nei Yoshihiro Soma
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C10
Mathematics Subject Classification ID: 11D04
zbMATH DE Number: 4027169
zbMATH Keywords: enumeration
zbMATH Keywords: one-dimensional knapsack problem
zbMATH Keywords: linear diophantine equations
zbMATH Keywords: pseudopolynomial
describes a project that uses: Algorithm 37
MaRDI profile type: Publication
cites work: Merging and Sorting Applied to the Zero-One Knapsack Problem
cites work: An Algorithm for Large Zero-One Knapsack Problems
cites work: Computational results with a branch-and-bound algorithm for the general knapsack problem
cites work: Hard Knapsack Problems
cites work: Discrete-Variable Extremum Problems
cites work: Shortest-Route Methods: 2. Group Knapsacks, Expanded Networks, and Branch-and-Bound
cites work: Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning
cites work: Resolution of the 0–1 knapsack problem: Comparison of methods
cites work: An algorithm for the solution of the 0-1 knapsack problem
cites work: Q4198056
cites work: A Linear Programming Approach to the Cutting Stock Problem—Part II
cites work: Multistage Cutting Stock Problems of Two and More Dimensions
cites work: The Theory and Computation of Knapsack Functions
cites work: Bounds on Multiprocessing Timing Anomalies
cites work: An algorithm for the computation of knapsack functions
cites work: Q5831392
cites work: Q3854871
cites work: Computing Partitions with Applications to the Knapsack Problem
cites work: Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
cites work: Polynomial-Time Aggregation of Integer Programming Problems
cites work: The knapsack problem: A survey
cites work: Fast Approximation Algorithms for Knapsack Problems
cites work: An upper bound for the zero-one knapsack problem and a branch and bound algorithm
cites work: Algorithm 37. Algorithm for the solution of the 0-1 single Knapsack problem
cites work: Worst-case analysis of greedy algorithms for the subset-sum problem
cites work: Technical Note—Computational Viability of a Constraint Aggregation Scheme for Integer Linear Programming Problems
cites work: Q3678962
cites work: Approximate Algorithms for the 0/1 Knapsack Problem
cites work: A Finite Renewal Algorithm for the Knapsack and Turnpike Models
cites work: Dynamic programming algorithms for the zero-one knapsack problem
Wikidata QID: Q127719690
description: scientific article; zbMATH DE number 4027169