An approximation scheme for bin packing with conflicts.

In this paper we consider the following bin packing problem with conflicts. Given a set of items V={1..., n} with sizes s1..., sn ∃ (0,1] and a conflict graph G=(V,E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j') ∃ E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem. We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ε) of optimal, and has a running time polynomial both in n and 1/ε. [ABSTRACT FROM AUTHOR]