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}>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 & 2.7 & 1.2\\
1.3 & 2.6 & 0.8\\
1.5 & 0.4 & 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}

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}>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*}
& {\underset{S}{\text{minimize}}}
& & |S|\\[3pt]
& \text{subject to}
& & \sum_{j'\in S\\j'\neq j} a_{ij'} \leqslant a_{ij}-1,\forall\, j\in
S,i\in K_j,\\[3pt]
& & & 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 & 4\\
3.1 & 3\\
5 & 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 > 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}

• 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.

StackExchange Computer Science Q#66382, answer score: 4