Inapproximability results for orthogonal rectangle packing problems with rotations

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution

94 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 languageEnglish
Title of host publicationAlgorithms and Complexity
Subtitle of host publication6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006. Proceedings
EditorsTiziana Calamoneri, Irene Finocchi, Guiseppe F. Italiano
PublisherSpringer
Chapter21
Pages199-210
Number of pages12
ISBN (Electronic)9783540343783
ISBN (Print)9783540343752
DOIs
Publication statusPublished - 2006
Event6th Italian Conference, CIAC 2006 - Rome, Italy
Duration: 29 May 200631 May 2006

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Number3998
ISSN (Print)0302-9743

Conference

Conference6th Italian Conference, CIAC 2006
Country/TerritoryItaly
CityRome
Period29/05/0631/05/06

Keywords

  • approximation hardness

Fingerprint

Dive into the research topics of 'Inapproximability results for orthogonal rectangle packing problems with rotations'. Together they form a unique fingerprint.

Cite this