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: [email protected] (P. Berman), [email protected] (B. DasGupta), [email protected] (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
SN - 0196-6774
VL - 47
SP - 122
EP - 134
JO - Journal of Algorithms
JF - Journal of Algorithms
IS - 2
ER -