×

Knapsack problems. (English) Zbl 1103.90003

Berlin: Springer (ISBN 3-540-40286-1/hbk). xx, 546 p. (2004).
The book starts with a basic introduction to the knapsack problem, the most frequently treated integer programming problem with a single constraint, where a subset of a certain number of items, each of them with its profit and weight, must be selected so that the total profit is maximized and the total weight remains below a certain capacity. It proceeds with a discussion about the basic techniques available for the solution to this problem, which makes it useful reading for undergraduate students of computer science, mathematics and economics.
The remaining chapters give an overview of the generalizations of the problem as well as the advanced algorithms for its solution. The best currently available exact algorithms, both from the point of view of complexity and the running time, as well as the approximation algorithms and heuristics are presented for a number of variations of the knapsack problem. The generalizations of the problem are illustrated by some applications. This part of the book represents good reading for graduate students of computer science and mathematics, but also for a reader willing to go into more depth of the problem.
At the end of the book, the authors provide a short presentation of the NP-completeness of the knapsack problem.
In conclusion, it could be said that the book is a valuable source for students, but also for researchers interested in this problem.

MSC:

90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C10 Integer programming
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
90C60 Abstract computational complexity for mathematical programming problems

Software:

Knapsack
PDFBibTeX XMLCite