Hardness of approximation for orthogonal rectangle packing and covering problems

Janka Chlebikova, M. Chlebik

Research output: Contribution to journalArticlepeer-review

71 Downloads (Pure)

Abstract

Bansal and Sviridenko [N. Bansal, M. Sviridenko, New approximability and inapproximability results for 2-dimensional bin packing, in: 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 Bin Packing (without rotations), unless P=NP. We show that similar approximation hardness results hold for several 2- and 3-dimensional rectangle packing and covering problems even if rotations by ninety degrees are allowed. Moreover, for some of these problems we provide explicit lower bounds on asymptotic approximation ratio of any polynomial time approximation algorithm. Our hardness results apply to the most studied case of 2-dimensional problems with unit square bins, and for 3-dimensional strip packing and covering problems with a strip of unit square base.
Original languageEnglish
Pages (from-to)291-305
Number of pages15
JournalJournal of Discrete Algorithms
Volume7
Issue number3
DOIs
Publication statusPublished - Sep 2009

Keywords

  • inapproximability results
  • orthogonal rectangle packing
  • packing and covering with rotations
  • rectangle covering

Fingerprint

Dive into the research topics of 'Hardness of approximation for orthogonal rectangle packing and covering problems'. Together they form a unique fingerprint.

Cite this