On the Knapsack Problem with a Conflict Graph 🗓 🗺

Speaker

Prof. Ulrich Pferschy  Università di Graz

Where and When

Mercoledì 10 Giugno 2015, ore: 15:00
Sala riunioni
Via della Vasca Navale 79 – Roma, Italy

Abstract

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)

Per informazioni:
Gaia Nicosia
tel. +390657333455 nicosia@ing.uniroma3.it