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?