Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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


area_perf_jour_revised.dvi (115.51 KB)

Journal

Journal Title*:

Acta Informatica

Journal's URL:

http://www.springerlink.com/content/100460/?p=e92e80bcba61403989c0a58a3ba56b0c&pi=0

Download URL
for the article:

http://www.springerlink.com/content/a0118866x7483576/fulltext.pdf

Language:

English

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, Abstract, ©

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},
ADDRESS = {Berlin},
MONTH = {January},
ISBN = {0001-5903},
DOI = {10.1007/s00236-007-0067-7},
}


Entry last modified by Rob van Stee, 03/03/2009
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Rob van Stee
Created
01/12/2009 01:03:13 PM
Revision
0.



Editor
Rob van Stee



Edit Date
01/12/2009 01:03:13 PM



Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
area_perf_jour_revised.dvi