Approximation algorithms for MAX-MIN tiling

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.