Next: MINIMUM RECTANGLE TILING
Up: Weighted Set Problems
Previous: MINIMUM SUM OF SQUARES
  Index
- 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].
Viggo Kann
1999-04-22