Paper Info
Title
Improved approximation algorithms for rectangle tiling and packing
Abstract
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.
Year
DOI
Venue
2001
10.5555/365411.365496
SODA
Keywords
Field
DocType
space input size,approximation ratio,improved approximation algorithm,approximation algorithm,rectangle tiling,domain size,np completeness,approximation algorithms,covering,manufacturing
Discrete mathematics,Approximation algorithm,Combinatorics,Lawn mowing,Packing problems,Largest empty rectangle,Rectangle,Mathematics
Conference
ISBN
Citations 
PageRank 
0-89871-490-7
15
0.89
References 
Authors
7
4
Name
Order
Citations
PageRank
Piotr Berman11754192.48
Bhaskar DasGupta255170.14
S. Muthukrishnan38025734.98
Suneeta Ramaswami422823.87