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

Question

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?

Answer 1

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.