TY - GEN
T1 - Slice and dice
T2 - 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
AU - Berman, Piotr
AU - DasGupta, Bhaskar
AU - Muthukrishnan, S.
PY - 2002
Y1 - 2002
N2 - We are given a two dimensional array A[l ... n, 1 ... n] where each A[i,j] stores a non-negative number. A (rectangular) tiling of A is a collection of rectangular portions A[l...r,t...b], called tiles, such that no two tiles overlap and each entry A[i, j] is contained in a tile. The weight of a tile is the sum of all array entries in it. In the MAX-MIN problem, we are given a weight bound W and our goal is to find a tiling such that (a) each tile is of weight at least W (the MIN condition) and (b) the number of tiles is maximized (the MAX condition). In the HIN-MAX problem, we are given a weight bound W again and our goal is to find a tiling such that (a) each tile has weight at most W and (b) the number of tiles is minimized. These two basic problems have many variations depending on the weight functions, whether some areas of A must not be covered, or whether some portion of A may be discarded, etc. These problems are not only natural combinatorial problems, but also arise in a plethora of applications, e.g., in databases and data mining, video compression, load balancing, building index structures, manufacturing and so forth. Both the above tiling problems (as well as all of their variations relevant to this paper) are known to be NP-hard. In this paper, we present approximations algorithms for solving these problems based on epicurean methods : variations of a basic slice-and-dice technique. Surprisingly, these simple algorithms yield small constant factor approximations for all these problems. For some of the problems, our results are the first known approximations; for others, our results improve the known algorithms significantly in approximation bounds and/or running time. Of independent interest are the tight bounds we show for sizes of the binary space partition trees for isothetic rectangles.
AB - We are given a two dimensional array A[l ... n, 1 ... n] where each A[i,j] stores a non-negative number. A (rectangular) tiling of A is a collection of rectangular portions A[l...r,t...b], called tiles, such that no two tiles overlap and each entry A[i, j] is contained in a tile. The weight of a tile is the sum of all array entries in it. In the MAX-MIN problem, we are given a weight bound W and our goal is to find a tiling such that (a) each tile is of weight at least W (the MIN condition) and (b) the number of tiles is maximized (the MAX condition). In the HIN-MAX problem, we are given a weight bound W again and our goal is to find a tiling such that (a) each tile has weight at most W and (b) the number of tiles is minimized. These two basic problems have many variations depending on the weight functions, whether some areas of A must not be covered, or whether some portion of A may be discarded, etc. These problems are not only natural combinatorial problems, but also arise in a plethora of applications, e.g., in databases and data mining, video compression, load balancing, building index structures, manufacturing and so forth. Both the above tiling problems (as well as all of their variations relevant to this paper) are known to be NP-hard. In this paper, we present approximations algorithms for solving these problems based on epicurean methods : variations of a basic slice-and-dice technique. Surprisingly, these simple algorithms yield small constant factor approximations for all these problems. For some of the problems, our results are the first known approximations; for others, our results improve the known algorithms significantly in approximation bounds and/or running time. Of independent interest are the tight bounds we show for sizes of the binary space partition trees for isothetic rectangles.
UR - http://www.scopus.com/inward/record.url?scp=84968830392&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84968830392&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84968830392
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 455
EP - 464
BT - Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002
PB - Association for Computing Machinery
Y2 - 6 January 2002 through 8 January 2002
ER -