## Abstract

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.

Original language | English (US) |
---|---|

Pages (from-to) | 122-134 |

Number of pages | 13 |

Journal | Journal of Algorithms |

Volume | 47 |

Issue number | 2 |

DOIs | |

State | Published - Jul 2003 |

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics