I have the following problem and I wonder if there exist a solution (or some algorithm to approximate it, even if it's far from optimal, as long as it is tractable) to it.

Say I have a set $V\subseteq I_1\times I_2 \times\dots\times I_n$, all discrete finite subset of, say, integers.

Can I compress the representation of $V$ (which currently use $|V| n$ entries) by representing it as the union of cartesian products of subsets of $V$?

For instance if $V = \{(1,1),(1,2),(1,3),(2,1),\dots,(3,3)\}$ we can also write is as $\{1,2,3\}\times \{1,2,3\}$ which uses fewer entries. We can do unions of those (they can overlap) but we cannot cover more than what's in $V$.

Finally, we allow only partial cartesian products, say $A\times B$ where $A\subseteq I_1\times I_3$ and $B\subseteq I_2\times I_4$. Or even no cartesian product. Note that under this constraint, $V$ itself is an admissible answer to the problem. But it may certainly be sub-optimal.

Any idea ? I don't even really know where to start or if this problem has a name.

Thanks a lot

  • $\begingroup$ Welcome to CS.SE! Can you make your question more precise? You can always express a set $V$ as the union of cartesian products of subsets, so the answer is always yes. In particular, for each element $(x_1,\dots,x_n) \in V$, you have a cartesian product of subsets $\{x_1\} \times \{x_2\} \times \cdots \times \{x_n\}$. Do you perhaps mean to ask about a union of minimal size? If so, you should edit the question to state that explicitly, and specify how do you define "size". $\endgroup$ – D.W. Jul 7 '17 at 22:31
  • $\begingroup$ Also, I couldn't understand what you mean by "partial cartesian products", so that part could probably use more explanation. $\endgroup$ – D.W. Jul 7 '17 at 22:31

Your Answer

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

Browse other questions tagged or ask your own question.