Compact knapsacks are polynomially solvable.

Hamid R. Amirazizi Ehud D. Karnin Justin M. Reyneri

Published in: SIGACT News (1983)

Keyphrases

polynomially solvable
np complete
special case
np hard
processing times
makespan minimization
knapsack problem
minimum cost
feasible solution
scheduling problem
linear programming
approximation algorithms
compact representations
optimal solution
genetic algorithm
data sets
branch and bound algorithm
training set