Next: Miscellaneous
Up: Compression and Representation
Previous: MAXIMUM COMMON POINT SET
  Index
- INSTANCE:
An n x n binary matrix.
- SOLUTION:
A collection of m rectangles that covers precisely those entries in
M that are 1's.
- MEASURE:
Size, i.e. number m of elements, of the collection.
- Good News:
Approximable within 14 [335].
- Garey and Johnson: SR25
Viggo Kann
1999-04-22