AN EFFICIENT PRUNING ALGORITHM FOR VALUE INDEPENDENT KNAPSACK-PROBLEMUSING A DAG STRUCTURE

Authors
SUN CH WANG SD
Citation
Ch. Sun et Sd. Wang, AN EFFICIENT PRUNING ALGORITHM FOR VALUE INDEPENDENT KNAPSACK-PROBLEMUSING A DAG STRUCTURE, Computers & operations research, 22(3), 1995, pp. 321-334
Citations number
10
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science","Computer Science Interdisciplinary Applications","Engineering, Industrial
Journal title
Computers & operations research → ACNP
ISSN journal
03050548
Volume
22
Issue
3
Year of publication
1995
Pages
321 - 334
Database
ISI
SICI code
0305-0548(1995)22:3<321:AEPAFV>2.0.ZU;2-O
Abstract
In this paper, we propose an efficient pruning algorithm to solve the value independent knapsack problem. It stores all the solutions in a d irected acyclic graph (DAG) using only O(M.n) space, where n is the pr oblem size and M is the subset summation. Our algorithm is suitable fo r the case of M<<2(n). Also, we find a symmetric property that can imp rove many heuristic algorithms proposed in the past.