On the Knapsack Problem with a Conflict Graph 🗓 🗺
Prof. Ulrich Pferschy Università di Graz
Where and When
Mercoledì 10 Giugno 2015, ore: 15:00
Via della Vasca Navale 79 – Roma, Italy
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)
tel. +390657333455 firstname.lastname@example.org