Inapproximability results for orthogonal rectangle packing problems with rotations

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/11758471_21

Inapproximability results for orthogonal rectangle packing problems with rotations

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

164 Downloads (Pure)

Abstract

Recently Bansal and Sviridenko [B & S, New approximability and inapproximability results for 2-dimensional bin packing, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196] proved that there is no asymptotic PTAS for 2-dimensional Orthogonal Rectangle Bin Packing without rotations allowed, unless P = NP. We show that similar approximation hardness results hold for several rectangle packing problems even if rotations by ninety degrees around the axes are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm.

Original language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings
Editors	Tiziana Calamoneri, Irene Finocchi, Guiseppe F. Italiano
Publisher	Springer
Chapter	21
Pages	199-210
Number of pages	12
ISBN (Electronic)	9783540343783
ISBN (Print)	9783540343752
DOIs	https://doi.org/10.1007/11758471_21
Publication status	Published - 2006
Event	6th Italian Conference, CIAC 2006 - Rome, Italy Duration: 29 May 2006 → 31 May 2006

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Number	3998
ISSN (Print)	0302-9743

Conference

Conference	6th Italian Conference, CIAC 2006
Country/Territory	Italy
City	Rome
Period	29/05/06 → 31/05/06

Keywords

approximation hardness

Access to Document

10.1007/11758471_21

Inapproximability results post-print
The final authenticated version is available online at: http://dx.doi.org/10.1007/11758471_21.
Accepted author manuscript (Post-print), 201 KB

Cite this

Chlebik, M., & Chlebikova, J. (2006). Inapproximability results for orthogonal rectangle packing problems with rotations. In T. Calamoneri, I. Finocchi, & G. F. Italiano (Eds.), Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings (pp. 199-210). (Lecture Notes in Computer Science; No. 3998). Springer. https://doi.org/10.1007/11758471_21

Chlebik, Miroslav ; Chlebikova, Janka. / Inapproximability results for orthogonal rectangle packing problems with rotations. Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. editor / Tiziana Calamoneri ; Irene Finocchi ; Guiseppe F. Italiano. Springer, 2006. pp. 199-210 (Lecture Notes in Computer Science; 3998).

@inproceedings{7995fec8a5034b639207f84d4601985e,

title = "Inapproximability results for orthogonal rectangle packing problems with rotations",

abstract = "Recently Bansal and Sviridenko [B & S, New approximability and inapproximability results for 2-dimensional bin packing, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196] proved that there is no asymptotic PTAS for 2-dimensional Orthogonal Rectangle Bin Packing without rotations allowed, unless P = NP. We show that similar approximation hardness results hold for several rectangle packing problems even if rotations by ninety degrees around the axes are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm.",

keywords = "approximation hardness",

author = "Miroslav Chlebik and Janka Chlebikova",

year = "2006",

doi = "10.1007/11758471_21",

language = "English",

isbn = "9783540343752",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

number = "3998",

pages = "199--210",

editor = "Tiziana Calamoneri and Irene Finocchi and Italiano, {Guiseppe F.}",

booktitle = "Algorithms and Complexity",

note = "6th Italian Conference, CIAC 2006 ; Conference date: 29-05-2006 Through 31-05-2006",

}

Chlebik, M & Chlebikova, J 2006, Inapproximability results for orthogonal rectangle packing problems with rotations. in T Calamoneri, I Finocchi & GF Italiano (eds), Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. Lecture Notes in Computer Science, no. 3998, Springer, pp. 199-210, 6th Italian Conference, CIAC 2006, Rome, Italy, 29/05/06. https://doi.org/10.1007/11758471_21

Inapproximability results for orthogonal rectangle packing problems with rotations. / Chlebik, Miroslav; Chlebikova, Janka.
Algorithms and Complexity: 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings. ed. / Tiziana Calamoneri; Irene Finocchi; Guiseppe F. Italiano. Springer, 2006. p. 199-210 (Lecture Notes in Computer Science; No. 3998).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Inapproximability results for orthogonal rectangle packing problems with rotations

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

PY - 2006

Y1 - 2006

N2 - Recently Bansal and Sviridenko [B & S, New approximability and inapproximability results for 2-dimensional bin packing, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196] proved that there is no asymptotic PTAS for 2-dimensional Orthogonal Rectangle Bin Packing without rotations allowed, unless P = NP. We show that similar approximation hardness results hold for several rectangle packing problems even if rotations by ninety degrees around the axes are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm.

AB - Recently Bansal and Sviridenko [B & S, New approximability and inapproximability results for 2-dimensional bin packing, Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2004, pp. 189–196] proved that there is no asymptotic PTAS for 2-dimensional Orthogonal Rectangle Bin Packing without rotations allowed, unless P = NP. We show that similar approximation hardness results hold for several rectangle packing problems even if rotations by ninety degrees around the axes are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm.

KW - approximation hardness

U2 - 10.1007/11758471_21

DO - 10.1007/11758471_21

M3 - Conference contribution

SN - 9783540343752

T3 - Lecture Notes in Computer Science

SP - 199

EP - 210

BT - Algorithms and Complexity

A2 - Calamoneri, Tiziana

A2 - Finocchi, Irene

A2 - Italiano, Guiseppe F.

PB - Springer

T2 - 6th Italian Conference, CIAC 2006

Y2 - 29 May 2006 through 31 May 2006

ER -

Inapproximability results for orthogonal rectangle packing problems with rotations

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this