Wednesday June 10th at 10:00 – On the Knapsack Problem with a Conflict Graph


Wednesday June 10th at 10:00


Department of Engineering
Section of Computer Science and Automation
Via della Vasca Navale, 79
Meeting room (1.10) on 1st floor


On the Knapsack Problem with a Conflict Graph


We consider the classical 0-1 Knapsack Problem with additional conflict restrictions on pairs of items, which state that for certain pairs of items at most one item can be contained in any feasible solution. This can also be seen as a Maximum Weight Independent Set Problem with an additional budget constraint. The conflicts between items can be represented by a conflict graph. We will give an overview on the status of approximability for different graph classes. In particular, we will describe an FPTAS for graphs of bounded treewidth and for (weakly) chordal graphs and a PTAS for planar graphs. Also modular and clique decompositions will be discussed leading to an FPTAS for certain graph classes characterized by forbidden subgraphs. (joint work with Joachim Schauer)