Tools
Chlebík, Miroslav and Chlebíková, Janka (2006) Inapproximability results for orthogonal rectangle packing problems with rotations. In: 6th Italian Conference on Algorithms and Complexity (CIAC 2006), Rome, ITALY.
Full text not available from this repository.Abstract
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.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Additional Information: | ALGORITHMS AND COMPLEXITY, PROCEEDINGS |
Schools and Departments: | School of Mathematical and Physical Sciences > Mathematics |
Depositing User: | Miroslav Chlebik |
Date Deposited: | 06 Feb 2012 20:32 |
Last Modified: | 11 Apr 2012 12:20 |
URI: | http://sro.sussex.ac.uk/id/eprint/26448 |