<p>The problem is NP-complete.
I sketch a reduction from 3-SAT.</p>

<p>Consider Boolean variables $x_1,\ldots,x_n$ and clauses $c_1,\ldots,c_m$ over these variables, so that each clause consists of three literals.  The question is to decide whether there exists a truth setting of the variables so that every single clause is satisfied (and hence contains at least one true literal).</p>

<p>We construct a matrix with $n+m+1$ rows and $2n+1$ columns.</p>

<ul>
<li>There is a special row $R^*$, and there is a special column $C^*$.</li>
<li>For every clause $c_j$, there is one corresponding row $R(c_j)$.</li>
<li>For every variable $x_i$, there is one corresponding row $R(x_i)$.</li>
<li>For every variale $x_i$, there are two corresponding columns $C^+(x_i)$ and $C^-(x_i)$.</li>
</ul>

<p>Let $Z=100(m+n)^{100}$ be a huge integer.</p>

<ul>
<li>The entry at the crossing of special column $C^*$ and special row $R^*$ is $1/Z^n$. All other entries in row $R^*$ take value $Z$. </li>
<li>All entries at a crossing of $C^*$ with a clause row $R(c_j)$ are $Z$.
All entries at a crossing of $C^*$ with a variable row $R(x_i)$ are $1/Z$.</li>
<li>The crossings of variable row $R(x_i)$ with columns $C^+(x_i)$ and $C^-(x_i)$ take value $Z$; all remaining entries in row $R(x_i)$ are $1$.</li>
<li>If clause $c_j$ contains the positive literal $x_i$, then the crossing of row $R(c_j)$ and column $C^+(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.</li>
<li>If clause $c_j$ contains the negative literal $\lnot x_i$, then the crossing of row $R(c_j)$ and column $C^-(x_i)$ is $1/Z$; all other entries in row $R(c_j)$ are $1$.</li>
</ul>

<p>It can be shown that the 3-SAT instance is satisfiable, if and only if the column selection problem has a solution $S$ for which the sum of products is at most $v=n+m+1$. Some comments:</p>

<ul>
<li>The set $S$ must contain the special column $C^*$; otherwise the contribution of the special row $R^*$ to the objective function (sum of products) is at least $Z&gt;v$.</li>
<li>The set $S$ can contain at most one of the two columns $C^+(x_i)$ and $C^-(x_i)$; otherwise the contribution of row $R(x_i)$ to the objective function will be at least $(1/Z)\cdot Z\cdot Z&gt;v$.</li>
<li>For every clause $c_j$, the set $S$ must contain some column $C^+(x_i)$ and $C^-(x_i)$ so that the corresponding literal $x_i$ respectively $\lnot x_i$ satisfies $c_j$. Otherwise, the contribution of row $R(c_j)$ to the objective function will be at least $Z&gt;v$.</li>
</ul>

CC BY-SA 3.0
2016-12-10T17:11:25.320Z
2016-12-10T17:17:08.087Z
2016-12-10T17:17:08.087Z
Gamow
<p>The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}&gt;0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not <em>all</em> greater than $1$ nor <em>all</em> less than one.</p>

<p>The question is to find a subset $S$ of $\{1,\ldots,n\}$ and $S\neq \emptyset$ such that $$\sum_{i=1}^k\prod_{j\in S}a_{ij}\leqslant v.$$</p>

<p>In fact, in the optimization settings, I would like to find a subset $S$ whose sum of products is minimum. </p>

<p><em>Example</em>: Take $v=0.55$ and $$\mathbf{A}=\begin{bmatrix} 0.1&amp;2&amp;3\\2&amp;0.2&amp;0.1\end{bmatrix}.$$ This has the solution $S=\{1,3\}$. Its value (its sum of products) is $0.5$.</p>

<p>How to solve this problem?  Is this problem known (or is there any similar problem in the literature)?</p>

<p>Besides enumerating all subsets of $\{1,\ldots,n\}$, I cannot find a good way to solve the problem.</p>

<cc.complexity-theory><ds.algorithms><reference-request>
How to find the "best vectors" in a given matrix whose sum of products is as small as possible?
drzbir
# How to find the "best vectors" in a given matrix whose sum of products is as small as possible?

(Asked by: username_0 on 2016-12-10)

The input is a matrix $\mathbf{A}=[a\_{ij}]$ of real numbers $a\_{ij}>0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not *all* greater than $1$ nor *all* less than one.

The question is to find a subset $S$ of $\{1,\ldots,n\}$ and $S\neq \emptyset$ such that $$\sum\_{i=1}^k\prod\_{j\in S}a\_{ij}\leqslant v.$$

In fact, in the optimization settings, I would like to find a subset $S$ whose sum of products is minimum.

*Example*: Take $v=0.55$ and $$\mathbf{A}=\begin{bmatrix} 0.1&2&3\\2&0.2&0.1\end{bmatrix}.$$ This has the solution $S=\{1,3\}$. Its value (its sum of products) is $0.5$.

How to solve this problem? Is this problem known (or is there any similar problem in the literature)?

Besides enumerating all subsets of $\{1,\ldots,n\}$, I cannot find a good way to solve the problem.

**Tags:** cc.complexity-theory, ds.algorithms, reference-request


---

## 1 answers

### Answer by username_1 on 2016-12-10. Score: 2 | Accepted answer

The problem is NP-complete.
I sketch a reduction from 3-SAT.

Consider Boolean variables $x\_1,\ldots,x\_n$ and clauses $c\_1,\ldots,c\_m$ over these variables, so that each clause consists of three literals. The question is to decide whether there exists a truth setting of the variables so that every single clause is satisfied (and hence contains at least one true literal).

We construct a matrix with $n+m+1$ rows and $2n+1$ columns.

* There is a special row $R^\*$, and there is a special column $C^\*$.
* For every clause $c\_j$, there is one corresponding row $R(c\_j)$.
* For every variable $x\_i$, there is one corresponding row $R(x\_i)$.
* For every variale $x\_i$, there are two corresponding columns $C^+(x\_i)$ and $C^-(x\_i)$.

Let $Z=100(m+n)^{100}$ be a huge integer.

* The entry at the crossing of special column $C^\*$ and special row $R^\*$ is $1/Z^n$. All other entries in row $R^\*$ take value $Z$.
* All entries at a crossing of $C^\*$ with a clause row $R(c\_j)$ are $Z$.
  All entries at a crossing of $C^\*$ with a variable row $R(x\_i)$ are $1/Z$.
* The crossings of variable row $R(x\_i)$ with columns $C^+(x\_i)$ and $C^-(x\_i)$ take value $Z$; all remaining entries in row $R(x\_i)$ are $1$.
* If clause $c\_j$ contains the positive literal $x\_i$, then the crossing of row $R(c\_j)$ and column $C^+(x\_i)$ is $1/Z$; all other entries in row $R(c\_j)$ are $1$.
* If clause $c\_j$ contains the negative literal $\lnot x\_i$, then the crossing of row $R(c\_j)$ and column $C^-(x\_i)$ is $1/Z$; all other entries in row $R(c\_j)$ are $1$.

It can be shown that the 3-SAT instance is satisfiable, if and only if the column selection problem has a solution $S$ for which the sum of products is at most $v=n+m+1$. Some comments:

* The set $S$ must contain the special column $C^\*$; otherwise the contribution of the special row $R^\*$ to the objective function (sum of products) is at least $Z>v$.
* The set $S$ can contain at most one of the two columns $C^+(x\_i)$ and $C^-(x\_i)$; otherwise the contribution of row $R(x\_i)$ to the objective function will be at least $(1/Z)\cdot Z\cdot Z>v$.
* For every clause $c\_j$, the set $S$ must contain some column $C^+(x\_i)$ and $C^-(x\_i)$ so that the corresponding literal $x\_i$ respectively $\lnot x\_i$ satisfies $c\_j$. Otherwise, the contribution of row $R(c\_j)$ to the objective function will be at least $Z>v$.


---

