An efficient pruning algorithm for value independent knapsack problem using a DAG structure
From MaRDI portal
Publication:1891244
DOI10.1016/0305-0548(94)00025-4zbMath0827.90110MaRDI QIDQ1891244
Publication date: 5 July 1995
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0305-0548(94)00025-4
90C09: Boolean programming
Cites Work
- Unnamed Item
- A Mixture of Dynamic Programming and Branch-and-Bound for the Subset-Sum Problem
- A Parallel Algorithm for the Knapsack Problem
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- 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
- A parallel time/hardware tradeoff T.H=O(2/sup n/2/) for the knapsack problem
- Technical Note—Solution of the Value-Independent Knapsack Problem by Partitioning