非表示:
キーワード:
-
要旨:
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, \ldots ,n\}$ with sides $s_1,s_2 \ldots ,s_n \in
[0,1]$ 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 $E=\emptyset$) and the graph coloring problem (in which
$s_i=0$ for all $i=1,2, \ldots ,n$). 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 $2+\eps$-approximation for bipartite graphs, which is
almost best possible (unless ${\mathit P=NP}$). For perfect
graphs, we design a 3.2744-approximation.
