zbMATH — the first resource for mathematics

New approximation algorithm for RTILE problem. (English) Zbl 1053.68127
Summary: For a given two-dimensional array of nonnegative numbers and a positive integer \(p\) we want to find a covering of the array with \(p\) tiles so as to minimize the weight of the heaviest tile. We present a \(\frac{9}{4}\) -approximation linear-time algorithm for this problem, which improves on the previous best result.

68W25 Approximation algorithms
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
Full Text: DOI
[1] M. Charikar, C. Chekuri, R. Motwani, unpublished.
[2] M. Grigni, F. Manne, On the complexity of generalized block distribution, in: Proc. 3rd Internat. Workshop on Parallel Algorithms for Irregularly Structured Problems (IRREGULAR’96), Lecture Notes in Computer Science, vol. 1117, Springer, Berlin, pp. 319-326.
[3] Han, Y.; Narahari, B.; Choi, H.-A., Mapping a chain task to chained processors, Inform. process. lett., 44, 141-148, (1992) · Zbl 0759.68027
[4] Khanna, S.; Muthukrishnan, S.; Paterson, M., On approximating rectangle tiling and packing, (), 384-393 · Zbl 0938.68928
[5] Khanna, S.; Muthukrishnan, S.; Skiena, S., Efficient array partitioning, (), 616-626 · Zbl 1401.68354
[6] K. Lorys, K. Paluch, Rectangle tiling, in: Proc. 3rd APPROX, Lecture Notes in Computer Science, vol. 1923, Springer, Berlin, pp. 206-213.
[7] G. Martin, S. Muthukrishnan, R. Packwood, I. Rhee, Fast algorithms for variable size block matching motion estimation with minimal error.
[8] Muthukrishnan, S.; Poosala, V.; Suel, T., On rectangular partitioning in two dimensionsalgorithms, complexity, and applications, (), 236-256
[9] J. Sharp, Tiling multi-dimensional arrays, in: Proc. 12th FCT, Lecture Notes in Computer Science, vol. 1684, Springer, Berlin, pp. 500-511.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.