# How to select a subset of columns in a given matrix to satisfy a condition?

Let $a_{kn}$ be positive real numbers for all $k\in\{1,\dots,K\}$ and $n\in\{1,\dots,N\}$ and let $t>0$. I need to find a subset $S$ of $\{1,\dots,N\}$ of minimum size such that:

• if $|S|=1$ then $a_{ki}\geq t$ for all $k\in\{1,\dots,K\}$ and $i\in S$.
• if $|S|>1$ then for all $k\in\{1,\dots,K\}$, there must exist some $i\in S$ such that $a_{ki}/a_{kj}\geq t$ for all $j\in S\backslash\{i\}$.

I need to find a good heuristic for this problem (an optimal if possible).

Example:

• let $t=2$; and
• the matrix $A$ given as:

$$A=\begin{pmatrix} 50 & 1 & 1\\ 1 & 70 & 1\\ 1 & 1 & 40\end{pmatrix}.$$

The set $S$ should be $\{1,2,3\}$.

To solve the problem, I need to enumerate all possible subsets of $\{1,\ldots,N\}$. Do you see any particular characteristic of the problem that I can use to solve it?

• If $a\ge 1$ then any element in $S$ should be chosen as the $i$ in your constraint for some $k$, otherwise it can be removed. It's only a pruning rule though, which might not be helpful. If $a<1$ in some entries I can't even come up with a heuristic... – aaaaajack Jan 18 '17 at 15:19
• Yes, you are right about this rule. Why do you think that designing heuristics for this problem is hard? – drzbir Jan 18 '17 at 15:36

The feasibility version of your problem is NP-complete, for any fixed $t > 1$, by reduction from SAT.

Suppose we are given a formula over the variables $x_1,\ldots,x_a$, having clauses $C_1,\ldots,C_b$. We will have $2a$ columns, one column per literal.

For each variable $x_i$ we will have the following row:

• Positions $x_i,\lnot x_i$ have value $1$, and all other columns have the value $1/t$.

This row forces the solution $S$ not to be a singleton, and forces it to contain exactly one of $\{x_i,\lnot x_i\}$.

For each clause $C_j = \ell_1 \lor \cdots \lor \ell_c$ we will have the following row:

• Positions $\ell_1,\ldots,\ell_c$ have values $1,1/t,\ldots,1/t^{c-1}$, and all other positions have value $1/t^c$.

This row forces the solution to contain at least one of the literals $\ell_1,\ldots,\ell_c$.

Conversely, any satisfying assignment corresponds to a set $S$, as can be easily checked. Hence a set $S$ exists iff the original formula is satisfiable.

• Thank you. Have you ever seen this problem or something similar before? As proved by your reduction I cannot hope to solve the problem optimally. However, I need to develop a heuristic for this, could you provide some related reference that I can use? – drzbir Jan 18 '17 at 23:55
• I don't recall having ever seen this problem. – Yuval Filmus Jan 19 '17 at 6:11
• Thank you anyway. I have a remark on your reduction. For example, the formula $(x\lor y)\land(\lnot x\lor\lnot z)$ is satisfiable with $y=1$ and $z=0$. The solution $y=1$ and $z=0$ corresponds to the columns $y$ and $\lnot z$. But we will have for some row $1/t$ on each column which violates the constraint. Or maybe there should be other satisfying variables like $x=1,y=1$ and $z=0$ that guarantees the constraints? – drzbir Jan 19 '17 at 20:10
• I only consider complete assignments, which are ones in which every variable is assigned some truth value. You can choose the value of $x$ whichever way you want in your example. – Yuval Filmus Jan 19 '17 at 20:50
• Nice. $\mathrm{}$ – drzbir Jan 19 '17 at 20:56