TY - GEN
T1 - Improved approximation algorithms for rectangle tiling and packing
AU - Berman, Piotr
AU - Dasgupta, Bhaskar
AU - Muthukrishnan, S.
AU - Ramaswami, Suneeta
PY - 2001
Y1 - 2001
N2 - We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE and d-RPACK) studied in the literature. Our algorithms are highly efficient since their running times are near-linear in the space input size rather than in the domain size. In addition, we improve the best known approximation ratios, in some cases quite significantly.
AB - We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE and d-RPACK) studied in the literature. Our algorithms are highly efficient since their running times are near-linear in the space input size rather than in the domain size. In addition, we improve the best known approximation ratios, in some cases quite significantly.
UR - https://www.scopus.com/pages/publications/0003661392
UR - https://www.scopus.com/pages/publications/0003661392#tab=citedBy
M3 - Conference contribution
AN - SCOPUS:0003661392
SN - 0898714907
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 427
EP - 436
BT - Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
T2 - 2001 Operating Section Proceedings, American Gas Association
Y2 - 30 April 2001 through 1 May 2001
ER -