@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",

}