  


Approximation of Knapsack Problems with Conflict and Forcing Graphs
Ulrich Pferschy(pferschyunigraz.at) Abstract: We study the classical 01 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. By modifying a recent result of Lokstanov et al. (2014) 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 Hminor free conflict graph is derived. This includes planar graphs and, more general, graphs of bounded genus. The PTAS is obtained by expanding a general result of Demaine et al. (2005). The knapsack problem with forcing graphs can be transformed into a minimization knapsack problem with conflict graphs. It follows immediately that all our FPTAS results of the current and a previous paper carry over from conflict graphs to forcing graphs. In contrast, the forcing graph variant is already inapproximable on planar graphs. Keywords: knapsack problem; conflict graph; weakly chordal graph; planar graph; graph decomposition Category 1: Combinatorial Optimization (Approximation Algorithms ) Category 2: Combinatorial Optimization (Graphs and Matroids ) Category 3: Integer Programming (01 Programming ) Citation: Download: [PDF] Entry Submitted: 11/21/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  