Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RECTANGLE COVERING:
Reports tagged with rectangle covering:
TR06-019 | 24th November 2005
Janka Chlebíková, Miroslav Chlebik

Hardness of asymptotic approximation for orthogonal rectangle packing and covering problems

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
more >>>




ISSN 1433-8092 | Imprint