Minimal set of Hyperrectangles covering an n-dimensional binary matrix with row permutations

Question

My input is a n-dimensional binary matrix.

My goal is to find the set of Hyperrectangles that covers every '1' at least once and covers not a single '0', which has minimal cardinality (the least amount of Hyperrectangles). The Hyperrectangles may overlap.

Before defining each next Hyperrectangle, I'm allowed to permute the 'rows' (along one or more dimensions) of the matrix.

An approximation algorithm will do, as long as it is always correct.

Is this problem reducible to some well-researched problem?

Answer 1

If "n-partitioned hypergraphs" are defined as "hypergraphs together with a partition of their vertices into n subsets such that each hyperedge has only one vertex from each of those subsets" then your problem can be reformulated as n-clique hyperdge-cover for n-uniform
n-partitioned hypergraphs, and that reformulation preserves approximations and the parameter
(when your problem is parametrized by number of hyperrectangles).

In particular, your problem is NP-hard to approximate, even for n=2.


Those problems are equivalent to:

Find [the assignment of one positive integer to each '1' in the matrix] such that with
C being the largest of those positive integers, [for all elements H of {1,2,3,...,C-1,C}
and all '0's in the matrix, there is a coordinate such that no '1' [with the
same value for that coordinate as the '0'] was assigned H], which minimizes C.


Thus, your problem can be solved in
((minimum_number_of_hyperrectangles)^(number_of_'1's)) * poly(input_size)
time with an embarassingly parallel workload.

Aside from the reformulation and the equivalent problem I mentioned,
I don't know of any problems that your problem is reducible to for any reason
other than your problem being in NPO and the other problem being NPO-hard.