How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time?
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.