# Kolloquiumsvortrag: PD Dr. Frank Gurski - Universität Düsseldorf/ 17.07.2015

17.07.2015 von 14:15 bis 15:45

Institut für Informatik, Ludewig-Meyn-Str. 2, Übungsraum 2

Titel: Knapsack Problems: A Parameterized point of view

Abstract:

The knapsack problem is a very famous NP-hard problem in combinatorial optimization. In the 0-1 knapsack problem (0-1 KP) we are given a set A of n items. Every item j has a profit p(j) and a size s(j). Further there is a capacity c of the knapsack. The task is to choose a subset A' of A, such that the total profit of A' is maximized and the total size of A' is at most c.

Within the d-dimensional 0-1 knapsack problem (d-KP) a set A of n items and a number d of dimensions is given. Every item j has a profit p(j) and for dimension i the size s(i,j). Further for every dimension i there is a capacity c(i). The goal is to find a subset A' of A, such that the total profit of A' is maximized and for every dimension i the total size of A' is at most the capacity c(i).

Further we consider the multiple 0-1 knapsack problem (MKP) where beside n items a number m of knapsacks is given. Every item j has a profit p(j) and a size s(j) and each knapsack i has a capacity c(i). The task is to choose m disjoint subsets of A such that the total profit of the selected items is maximized and each subset can be assigned to a different knapsack i without exceeding its capacity c(i) by the sizes of the selected items.

Since d-KP and MKP are 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. 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 pseudopolynomial algorithms.