3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Do the hypercubes all need to be n-dimensional? $\;$ $\endgroup$ – user6973 Jul 9 '15 at 8:24
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.