English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Two-dimensional Packing with Conflicts

MPS-Authors
/persons/resource/persons45543

van Stee,  Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Epstein, L., Levin, A., & van Stee, R. (2008). Two-dimensional Packing with Conflicts. Acta Informatica, 45(3), 155-175. doi:10.1007/s00236-007-0067-7.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1D4D-C
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, \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.