How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time? The real problem I am facing is the following.

INSTANCE: I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}&gt;0$ for all $i\in K$ and $j\in N$. 

QUESTION: I need to find a subset $S$ of $N$ of size as small as possible and partition the set $K$ into $|S|$ disjoint sets $K_j$ whose union equals $K$ such that for all $j\in S$, I have $$\sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,$$ for all $i\in K_j$. 

Example:

Given $n=k=3$ and the matrix 
$$
\begin{bmatrix}
0.6 &amp; 2.7 &amp; 1.2\\
1.3 &amp; 2.6 &amp; 0.8\\
1.5 &amp; 0.4 &amp; 0.6 
\end{bmatrix}.
$$

In this example, $S$ should be equal to $S=\{1, 2\}$ and $K_1=\{3\}$ and $K_2=\{1,2\}$.

I noticed two facts:


If there exists some $j\in N$ such that $a_{ij}\geqslant 1$ for all $i\in K$ then $S=\{j\}$ and $K_j=K$; and
If there exists some $i\in K$ such that $a_{ij}&lt;1$ then $S=\emptyset$.


My question:
Is it possible to solve this optimization problem in polynomial time (at least with approximation algorithm)?

The first thing I tried to do is to transform it into a known problem and then applied a known algorithm for that. I thought about transforming it to a set cover or bin packing but I failed and also I do not think that this is interesting. 



The problem I tried to formulate.

I have sets $N:=\{1,\ldots,n\}$ and $K:=\{1,\ldots,k\}$ and matrix $a_{ij}&gt;0$ for all $i\in K$ and $j\in N$. Also, I have $n$ disjoints  sets $K_j\subset K$ for each $j\in N$, (I added $K_j$ as inputs because I could not formulate it otherwise.)

Finally, I get this:
$$
    \begin{align*}
      &amp; {\underset{S}{\text{minimize}}}
      &amp; &amp; |S|\\[3pt]
      &amp; \text{subject to} 
      &amp; &amp; \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in 
S,i\in K_j,\\[3pt]
      &amp; &amp; &amp; S\subseteq N.\\
    \end{align*}
$$

Thanks.
Even the decision version of this problem, in which we try to determine simply if there exists any feasible solution, is NP-hard by reduction from Exact Cover.  (The optimisation version, where we seek a feasible solution that minimises $|S|$, is clearly at least as hard as this.)

The single-row, single-column matrix containing the value 0.5 is an example of an input for which there is no feasible solution.  Here's another:

$$
\begin{bmatrix}
0.2 &amp; 4\\
3.1 &amp; 3\\
5 &amp; 0.6
\end{bmatrix}.
$$

Building a "Choose at most one" gadget

First, notice that if the maximum value in some row $a_i$ is $x &gt; 0$, and this row contains (at least) two copies of $x$, say at $a_{ij}$ and $a_{ij'}$, $j' \ne j$, then $S$ cannot contain both $j$ and $j'$, since if it did then one of the following two cases must arise, each of which leads to a contradiction:


$i \in K_j \cup K_{j'}$: Suppose w.l.o.g. that $i \in K_j$.  But then $\Sigma_{m \in S, m \ne j}{a_{im}} \ge a_{ij'} = x = a_{ij}$, contradicting the requirement that $\Sigma_{m \in S, m \ne j}{a_{im}} \le a_{ij} - 1$.
$i \notin K_j \cup K_{j'}$: Then suppose $i \in K_p, p \notin \{j, j'\}$.  But then $\Sigma_{m \in S, m \ne p}{a_{im}} \ge a_{ij} + a_{ij'} = 2x$, and since $x$ is maximal in row $i$, the highest that $a_{ip}$ could be is clearly $x$, so we must be violating the same inequality as before.


Thus we can choose some maximum value that is safely higher than the sum of all non-maximum values in the row, and use copies of this maximum value to enforce that at most one of those columns is included in $S$.

We can turn this "choose at most one" constraint into a "choose exactly one" constraint by using any positive value less than 1 as the "non-maximum" value.  That's because every row $i$ belongs to some part $K_j$ of the row partition, and if $a_{ij} &lt; 1$ then the RHS of the inequality becomes negative for row $i$, so there is no way to satisfy it: thus at least one $j$ must be forced into $S$ such that $a_{ij} \ge 1$.

So, to ensure that exactly one of the columns in some set $T \subseteq N$ is forced into $S$, create a row $a_i$ as follows:


Set $a_{ij} = n+1$ for each $j \in T$.
Set $a_{ij} = 0.5$ for every other $j$.


Thus the reduction from Exact Cover is straightforward: there is a row for each element, a column for each set, with $a_{ij} = n+1$ whenever set $j$ includes element $i$ and $a_{ij} = 0.5$ otherwise.  Both directions ("Input EC instance is a YES-instance $\implies$ constructed instance of OP's problem is a YES-instance", and "Constructed instance of OP's problem is a YES-instance $\implies$ input EC instance is a YES-instance") are clear.