6
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – aaaaajack Jan 18 '17 at 15:19
  • $\begingroup$ Yes, you are right about this rule. Why do you think that designing heuristics for this problem is hard? $\endgroup$ – drzbir Jan 18 '17 at 15:36
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – drzbir Jan 18 '17 at 23:55
  • $\begingroup$ I don't recall having ever seen this problem. $\endgroup$ – Yuval Filmus Jan 19 '17 at 6:11
  • $\begingroup$ 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? $\endgroup$ – drzbir Jan 19 '17 at 20:10
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jan 19 '17 at 20:50
  • $\begingroup$ Nice. $\mathrm{}$ $\endgroup$ – drzbir Jan 19 '17 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.