TY - JOUR

T1 - Approximation algorithms for MAX-MIN tiling

AU - Berman, Piotr

AU - DasGupta, Bhaskar

AU - Muthukrishnan, S.

N1 - Funding Information:
✩ The preliminary version of these results appeared in 13th ACM–SIAM Annual Symposium on Discrete Algorithms, January 6–8, 2002, pp. 455–464. * Corresponding author. E-mail addresses: berman@cse.psu.edu (P. Berman), dasgupta@cs.uic.edu (B. DasGupta), muthu@research.att.com (S. Muthukrishnan). 1 Supported in part by NSF grant CCR-9700053 and NLM grant LM05110. 2 Supported in part by NSF grants CCR-0296041, CCR-0206795 and CCR-0208749, and a UIC startup fund.

PY - 2003/7

Y1 - 2003/7

N2 - The MAX-MIN tiling problem is as follows. We are given A[1,..., n][1,..., n], a two-dimensional array where each entry A[i][j] stores a non-negative number. Define a tile of A to be a subarray A[l,..., r][t,..., b] of A, the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A[i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX-MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at leant W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX-MIN tiling problem is known to be NP-hard; here, we present first non-trivial approximations algorithms for solving it.

AB - The MAX-MIN tiling problem is as follows. We are given A[1,..., n][1,..., n], a two-dimensional array where each entry A[i][j] stores a non-negative number. Define a tile of A to be a subarray A[l,..., r][t,..., b] of A, the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A[i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX-MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at leant W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX-MIN tiling problem is known to be NP-hard; here, we present first non-trivial approximations algorithms for solving it.

UR - http://www.scopus.com/inward/record.url?scp=0037635116&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0037635116&partnerID=8YFLogxK

U2 - 10.1016/S0196-6774(03)00015-4

DO - 10.1016/S0196-6774(03)00015-4

M3 - Article

AN - SCOPUS:0037635116

VL - 47

SP - 122

EP - 134

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 2

ER -