Knapsack problems: algorithms and computer implementations
Here is a state of art examination on exact and approximate algorithms for a number of important NP-hard problems in the field of integer linear programming, which the authors refer to as ``knapsack.'' Includes not only the classical knapsack problems such as binary, bounded, unbounded or binary multiple, but also less familiar problems such as subset-sum and change-making. Well known problems that are not usually classified in the knapsack area, including generalized assignment and bin packing, are also covered. The text fully develops an algorithmic approach without losing mathematical rigor.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Bounded knapsack problem
6 other sections not shown
0-1 knapsack problem 0-1 multiple knapsack 0-1 single knapsack 20 problems approximate algorithms approximate solution arg max arrays assigned backtracking begin binary branch-and-bound algorithm CDC-Cyber computational experiments constraints continuous relaxation core problem corresponding critical item current solution decision-tree defined determine dominates dynamic programming end end exact algorithms exact exact feasible solution given greedy algorithm Hence input parameters integer linear programming item types items of type iteration Lagrangian relaxation length at least lower bound Martello and Toth maximize minimization MTC1 MTHG MTSL NP-complete NP-hard number of items obtained optimal solution value output Pj/wj polynomial-time approximation scheme positive integers residual capacity single knapsack problem solution found solution of value solve sorted according space complexity subroutine subset subset-sum Table Theorem unbounded knapsack upper bound variables vector weight wj uniformly random wjxj wjxy worst-case performance ratio