Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2023) | last year (2022) | two years ago (2021) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Epstein, Leah Levin, Asaf van Stee, Rob dblp dblp dblp Not MPG Author(s): Epstein, Leah Levin, Asaf
 BibTeX cite key*: vanStee2008e

 Title
 Title*: Two-dimensional packing with conflicts Attachment(s): area_perf_jour_revised.dvi (115.51 KB)

 Journal

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springer-ny.com/ Publisher's Address: Berlin ISSN: 0001-5903

 Vol, No, pp, Date
 Volume*: 45 Number: 3 Publishing Date: January 2008 Pages*: 155-175 Number of VG Pages: 21 Page Start: Page End: Sequence Number: DOI: 10.1007/s00236-007-0067-7

 Note: (LaTeX) 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. URL for the Abstract: Categories, Keywords: bin packing, approximation algorithms HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{vanStee2008e,
AUTHOR = {Epstein, Leah and Levin, Asaf and van Stee, Rob},
TITLE = {Two-dimensional packing with conflicts},
JOURNAL = {Acta Informatica},
PUBLISHER = {Springer},
YEAR = {2008},
NUMBER = {3},
VOLUME = {45},
PAGES = {155--175},