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

• Have you tried reformulating as an ILP by using binary variables $x_j$? Your objective changes to min $\sum x_j$ with a similar change int he constraint. An off-the-shelf ILP solver may handle it just fine. Nov 24, 2016 at 2:55
• But I think that would not give me a polynomial time algorithm? Nov 24, 2016 at 3:36
• Maybe in theory, but not in practice. Modern solvers like CPLEX are incredibly good at finding optimal solutions in a relatively short time thanks to branch and bound and other heuristics. Nov 24, 2016 at 4:44
• Are the $a_{ij}$ all $\ge 1$? If so, then I think the formulation of your "real problem" has a problem, since it's trivially optimised by letting $S$ be any singleton set $\{j\}$: doing this causes the summation on the LHS of your objective function to be 0. Nov 24, 2016 at 8:06
• Not all $a_{ij}$ are greater than $1$. Nov 24, 2016 at 13:47

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.

• The $2\times2$ example you gave I think has a solution of $S=\{2\}$. Nov 24, 2016 at 17:45
• I have $S=\{2\}$ and $K_2=K=\{1,2\}$. So my inequality is $0\leqslant a_{i2}-1$ for $i\in K_2=\{1,2\}$. Because the inequality must be valid for all $i\in K_j$. Nov 24, 2016 at 17:59
• You're right, sorry. I'll fix it now. Nov 24, 2016 at 18:00
• I have written this problem as integer program and I solved it. Now, I need to solve it with a greedy algorithm (better, an algorithm with a performance guarantees). As you suggested, I looked for exact cover hopping to found ideas how to design a good algorithm for this. Do you have any ideas? Nov 24, 2016 at 19:44
• It's NP-hard, so almost certainly no poly-time algorithm exists. I would try checking all single columns, all pairs of columns, all triples etc. until you find a satisfying set. The subproblem you need to solve for each row (namely, deciding which element in $S$ to pick for this row) is easy. Nov 25, 2016 at 10:19