  The knapsack problem (KP) is a very famous NP-hard problem in combinatorial
optimization. Also its generalization to multiple dimensions named
d-dimensional knapsack problem (d-KP) and to multiple knapsacks named multiple
knapsack problem (MKP) are well known problems. Since KP, d-KP, and MKP are
integer-valued problems defined on inputs of various informations, we study the
fixed-parameter tractability of these problems. The idea behind fixed-parameter
tractability is to split the complexity into two parts - one part that depends
purely on the size of the input, and one part that depends on some parameter of
the problem that tends to be small in practice. Further we consider the closely
related question, whether the sizes and the values can be reduced, such that
their bit-length is bounded polynomially or even constantly in a given
parameter, i.e. the existence of kernelizations is studied. We discuss the
following parameters: the number of items, the threshold value for the profit,
the sizes, the profits, the number d of dimensions, and the number m of
knapsacks. We also consider the connection of parameterized knapsack problems
to linear programming, approximation, and pseudo-polynomial algorithms.
