@article{7f71eeb56b8f478597cea2ee30118e9f,
title = "Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles",
abstract = "We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE, and d-RPACK) studied in the literature. Most of our algorithms are highly efficient since their running times are near-linear in the sparse input size rather than in the domain size. In addition, we improve the best known approximation ratios.",
author = "Piotr Berman and Bhaskar DasGupta and S. Muthukrishnan and Suneeta Ramaswami",
note = "Funding Information: We provide improved approximation algorithms for several rectangle tiling and packing problems (RTILE, DRTILE, and d-RPACK) studied in the literature. Most of our algorithms are highly efficient since their running times are near-linear in the sparse input size rather than in the domain size. In addition, we improve the best known approximation ratios. 2001 Elsevier Science 1A preliminary version of this paper appeared in 12th ACM-SIAM Symposium on Discrete Algorithms, January 2001, pp. 427–436. 2Supported in part by NSF grant CCR-9700053 and by NLM grant LM05110. 3Supported in part by NSF grant CCR-9800086.",
year = "2001",
month = nov,
doi = "10.1006/jagm.2001.1188",
language = "English (US)",
volume = "41",
pages = "443--470",
journal = "Journal of Algorithms",
issn = "0196-6774",
publisher = "Academic Press Inc.",
number = "2",
}