The Knapsack Problem with Conflict Graphs

Ulrich Pferschy (pferschyuni-graz.at)
Joachim Schauer (joachim.schaueruni-graz.at)

Abstract: We extend the classical 0-1 knapsack problem by introducing disjunctive constraints for pairs of items which are not allowed to be packed together into the knapsack. These constraints are represented by edges of a conflict graph whose vertices correspond to the items of the knapsack problem. Similar conditions were treated in the literature for bin packing and scheduling problems. For the knapsack problem with conflict graph exact and heuristic algorithms were proposed in the past. While the problem is strongly NP-hard in general, we present pseudopolynomial algorithms for three special graph classes, namely trees, graphs with bounded treewidth and chordal graphs. From these algorithms we can easily derive fully polynomial time approximation schemes (FPTAS).

Keywords: knapsack problem, conflict graph

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Integer Programming (0-1 Programming )

Citation: Journal of Graph Algorithms and Applications, Vol. 13, no. 2, pp. 233-249, 2009. http://jgaa.info/accepted/2009/PferschySchauer2009.13.2.pdf

Download:

Entry Submitted: 10/30/2008
Entry Accepted: 10/30/2008
Entry Last Modified: 12/16/2009

Modify/Update this entry