Preface
Thirteen years have passed since the seminal book on knapsack problems by
Martello and Toth appeared. On this occasion a former colleague exclaimed back
in 1990: "How can you write 250 pages on the knapsack problem?" Indeed, the
definition
of
the knapsack problem is easily understood even by a non-expert who
will not suspect the presence
of
challenging research topics in this area at the first
glance.
However, in the last decade a large number
of
research publications contributed new
results for the knapsack problem in all areas
of
interest such as exact algorithms,
heuristics and approximation schemes. Moreover, the extension
of
the knapsack
problem to higher dimensions both in the number
of
constraints and in the num-
ber
of
knapsacks, as well as the modification
of
the problem structure concerning
the available item set and the objective function, leads to a number
of
interesting
variations
of
practical relevance which were the subject
of
intensive research during
the last few years.
Hence, two years ago the idea arose to produce a new monograph covering not only
the most recent developments
of
the standard knapsack problem, but also giving a
comprehensive treatment
of
the whole knapsack family including the siblings such
as the subset sum problem and the bounded and unbounded knapsack problem, and
also more distant relatives such as multidimensional, multiple, multiple-choice and
quadratic knapsack problems in dedicated chapters.
Furthermore, attention is paid to a number
of
less frequently considered variants
of
the knapsack problem and to the study
of
stochastic aspects
of
the problem.
To
illustrate the high practical relevance
of
the knapsack family for many industrial and
economic problems, a number
of
applications are described in more detail. They
are selected subjectively from the innumerable occurrences
of
knapsack problems
reported in the literature.
Our above-mentioned colleague will be surprised to notice that even
on
the more
than 500 pages
of
this book not all relevant topics could be treated in equal depth
but decisions had to
be
made on where to go into details
of
constructions and proofs
and where to concentrate on stating results and refer to the appropriate publications.
Moreover, an editorial deadline had to be drawn at some point. In our case, we
stopped looking for new publications at the end
of
June 2003.
111111111
22222222
