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.

REFERENCES

• BNR96: Vineet Bafna , Babu Narayanan , R. Ravi, Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles), Discrete Applied Mathematics, v.71 n.1-3, p.41-53, Dec. 5, 1996 [doi>10.1016/S0166-218X(96)00063-7]
• FM+96a: Takeshi Fukuda , Yasukiko Morimoto , Shinichi Morishita , Takeshi Tokuyama, Data mining using two-dimensional optimized association rules: scheme, algorithms, and visualization, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.13-23, June 04-06, 1996, Montreal, Quebec, Canada
• FM+96b: Takeshi Fukuda , Yasuhido Morimoto , Shinichi Morishita , Takeshi Tokuyama, Mining optimized association rules for numeric attributes, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.182-191, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237708]
• FPT81: R. Fowler, M. Paterson, and S. Tanimoto. Optimal packing and covering in the plane are np-complete. Information Proc. Letters, 12, 133-137, 1981.
• KMP98: Sanjeev Khanna , S. Muthukrishnan , Mike Paterson, On approximating rectangle tiling and packing, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.384-393, January 25-27, 1998, San Francisco, California, United States
• K80: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• LP00: Krzysztof Lorys , Katarzyna Paluch, Rectangle tiling, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization, p.206-213, September 05-08, 2000
• MD88: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• MPS99: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceeding of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• O88: M. H Overmars. Computational geometry on a grid: an overview, Theoretical Foundations of Computer Graphics and CAD. NATO ASI Series F40, Edited by R. A. Earushaw, Springer-Verlag Berlin Heidelberg, 167-184, 1988.
• P97: Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
• RS99: R. Rastogi and K. Shim Mining optimized support rules for numerical attributes. Proc. intl Conf. Data Engineering, 1999.
• S99: Jonathan P. Sharp, Tiling Multi-dimensional Arrays, Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, p.500-511, August 30-September 03, 1999
• SS99: Adam Smith , Subhash Suri, Rectangular tiling in multi-dimensional arrays, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.786-794, January 17-19, 1999, Baltimore, Maryland, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Computations on discrete structures

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification