File(s) not publicly available
Hardness of approximation for orthogonal rectagle packing and covering problems
journal contribution
posted on 2023-06-07, 20:40 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková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.
History
Publication status
- Published
Journal
Journal of Discrete AlgorithmsISSN
1570-8667External DOI
Issue
3Volume
7Page range
291-305Pages
15.0Department affiliated with
- Mathematics Publications
Full text available
- No
Peer reviewed?
- Yes
Legacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC