Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-019 | 24th November 2005 00:00

Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

RSS-Feed

Abstract:

Recently Bansal and Sviridenko (Proc. of the 15th SODA'04, 189-196)
proved that for
2-dimensional Orthogonal Rectangle
Bin Packing without rotations allowed there is no asymptotic PTAS, unless P=NP. We show that similar
approximation hardness results hold for several rectangle packing and covering 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.



ISSN 1433-8092 | Imprint