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" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Viagra has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.