Wednesday, 16:15 - 16:40 h, Room: H 3004


Joachim Schauer
Knapsack problems with disjunctive constraints

Coauthor: Ulrich Pferschy


We study the classical 0-1 knapsack problem subject to binary disjunctive constraints. Conflict constraints state that certain pairs of items cannot be simultaneously contained in a feasible solution. Forcing constraints enforce at least one of the items of each given pair to be included into the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs. We will derive FPTASs for the knapsack problem with chordal forcing graphs and with forcing graphs of bounded treewidth - complementing results for the conflict graph case given in Pferschy and Schauer (2009). The result for chordal forcing graphs is derived by a transformation of the problem into a minimization knapsack problem with chordal conflict graphs. We will furthermore give a PTAS for the knapsack problem with planar conflict graphs. In contrast the corresponding forcing graph problem is inapproximable. Similar complexity results are given for
subclasses of perfect graphs as conflict (resp. forcing) graphs.


Talk 3 of the contributed session Wed.3.H 3004
"Knapsack and bin packing" [...]
Cluster 2
"Combinatorial optimization" [...]


  personal loan . Moreover, to order Cialis Daily online is highly advantageous because it interacts well with the small portions of alcohol and food.