File(s) not publicly available
Inapproximability results for orthogonal rectangle packing problems with rotations
presentation
posted on 2023-06-08, 06:38 authored by Miroslav ChlebikMiroslav Chlebik, Janka ChlebíkováRecently Bansal and Sviridenko [4] 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.
History
Publication status
- Published
ISSN
0302-9743Publisher
SPRINGER-VERLAG BERLIN, HEIDELBERGERVolume
LNCS 3Pages
12.0Presentation Type
- paper
Event name
6th Italian Conference on Algorithms and Complexity (CIAC 2006)Event location
Rome, ITALYEvent type
conferenceISBN
3-540-34375-XDepartment affiliated with
- Mathematics Publications
Notes
ALGORITHMS AND COMPLEXITY, PROCEEDINGSFull text available
- No
Peer reviewed?
- Yes
Editors
GF Italiano, T Calamoneri, I FinocchiLegacy Posted Date
2012-02-06Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC