Next: MINIMUM RECTANGLE TILING Up: Weighted Set Problems Previous: MINIMUM SUM OF SQUARES Index

### MINIMUM ARRAY PARTITION

- INSTANCE: An n x n array A of non-negative integers, and a positive integer p.

- SOLUTION: p-1 horizontal dividers and p-1 vertical dividers partitioning A into p2 blocks.

- MEASURE:

- Good News: In APX [292].

- Bad News: Not approximable within less than 2 [193].

- Comment: The good news is valid also for generalizations to higher dimensions and other measures. The dual problem, where a limit is given instead of p, and where the problem is to find the minimum p such that the array can be partitioned into p2 blocks where each block's measure is bounded by , is approximable within [292].