Assume you are given a matrix $$ X= \begin{bmatrix} x_1^1 & x_1^2 & \dots & x_1^m \\ x_2^1 & x_2^2 & \dots & x_2^m \\ \vdots & \vdots & \ddots & \vdots \\ x_n^1 & x_n^2 & \dots & x_n^m \end{bmatrix} $$ such that all $x_i^j \in \big\{0,1\big\}$, $\vee$ is the logical OR, and: $$ \forall i,j, \quad x_{i}^j = \begin{cases} x_{i+1}^{j}\vee x_{i+1}^{j-1} & \text{if }\:j\neq1,\\ x_{i+1}^1\vee x_{i}^m & \text{otherwise}. \end{cases} $$ This is quite similar to the Pascal triangle with binomials, except here we are dealing with $0/1$ variables and regular addition is replaced by the logical OR.

The problem now is to minimize: $$S=\sum_{i,j} x_i^j,$$ where the trivial case $S=0$ with all $x_i^j=0$ is not an option. The sum is the one in the integers: $0<S\leq n m$.

EDIT: What can we say about the case where the $\vee$ operator is no longer the logical OR, but is defined by: $0\vee0=0$, $1\vee0=0\vee1=1$ and $1\vee1\in\{0,1\}$.

Does this problem reduces to another one? Maybe there are references that I am not aware of.

Thanks for your help.

  • $\begingroup$ How is $x_i^j$ defined for $i=n$? And: is it really $x_i^m$ in the second of the definition? $\endgroup$ – Marcus Ritt Mar 2 '12 at 10:36
  • $\begingroup$ When $i=n$, there is no constraint: values are free to choose. And yes, it is $x_i^m$: there is this linking property the Pascal triangle does not have. $\endgroup$ – wwjoze Mar 4 '12 at 11:48

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.