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

📧 Request an update