Two-dimensional packing with conflicts |
| |
Authors: | Leah Epstein Asaf Levin Rob van Stee |
| |
Affiliation: | (1) Department of Mathematics, University of Haifa, Haifa, 31905, Israel;(2) Department of Statistics, The Hebrew University, Jerusalem, 91905, Israel;(3) Department of Computer Science, University of Karlsruhe, 76128 Karlsruhe, Germany |
| |
Abstract: | We study the two-dimensional version of the bin packing problem with conflicts. We are given a set of (two-dimensional) squares
V = {1, 2, . . . ,n} with sides and a conflict graph G = (V, E). We seek to find a partition of the items into independent sets of G, where each independent set can be packed into a unit square bin, such that no two squares packed together in one bin overlap.
The goal is to minimize the number of independent sets in the partition. This problem generalizes the square packing problem
(in which we have ) and the graph coloring problem (in which s
i
= 0 for all i = 1,2, . . . , sn). It is well known that coloring problems on general graphs are hard to approximate. Following previous work on the one-dimensional
problem, we study the problem on specific graph classes, namely, bipartite graphs and perfect graphs. We design a -approximation for bipartite graphs, which is almost best possible (unless P = NP). For perfect graphs, we design a 3.2744-approximation.
An extended abstract version of this paper has appeared in Proceedings of the 16th International Symposium on Fundamentals
of Computation Theory (FCT 2007), pp 288–299.
Rob van Stee was supported by the Alexander von Humboldt Foundation. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|