Approximation of Knapsack Problems with Conflict and Forcing Graphs
We study the classical 0-1 knapsack problem with additional restrictions on pairs of items. A conflict constraint states that from a certain pair of items at most one item can be contained in a feasible solution. Reversing this condition, we obtain a forcing constraint stating that at least one of the two items must be included in the knapsack. A natural way for representing these constraints is the use of conflict (resp. forcing) graphs.
We derive a fairly complicated FPTAS for the knapsack problem on weakly chordal conflict graphs. Next, we show that the techniques of modular decompositions and clique separators, widely used in the literature for solving the independent set problem on special graph classes, can be applied to the knapsack problem with conflict graphs. In particular, we can show that every positive approximation result for the atoms of prime graphs arising from such a decomposition carries over to the original graph. We point out a number of structural results from the literature which can be used to show the existence of an FPTAS for several graph classes characterized by the exclusion of certain induced subgraphs. Finally, a PTAS for the knapsack problem with H-minor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus.
Pferschy, U. und Schauer, J. (2017): Approximation of Knapsack Problems with Conflict and Forcing Graphs, in: Journal of Combinatorial Optimization, Vol. 33, No. 4, pp. 1300-1323.
Weitere Publikationen finden Sie hier.