How to minimize the cardinality of a set and disjoint partitions subject to constraints in polynomial time?

Question

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

Answer 1

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:

1. $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$.
2. $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} < 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.