- INSTANCE:
An
array
*A*of non-negative integers, and a positive integer*p*. - SOLUTION:
*p-1*horizontal dividers and*p-1*vertical dividers partitioning*A*into blocks. - MEASURE:

*Good News:*In APX [307].*Bad News:*Not approximable within less than 2 [205].*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 blocks where each block's measure is bounded by , is approximable within [307].