8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Nicholas Mancuso Nov 24 '16 at 2:55
  • $\begingroup$ But I think that would not give me a polynomial time algorithm? $\endgroup$ – drzbir Nov 24 '16 at 3:36
  • $\begingroup$ 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. $\endgroup$ – Nicholas Mancuso Nov 24 '16 at 4:44
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Nov 24 '16 at 8:06
  • $\begingroup$ Not all $a_{ij}$ are greater than $1$. $\endgroup$ – drzbir Nov 24 '16 at 13:47
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The $2\times2$ example you gave I think has a solution of $S=\{2\}$. $\endgroup$ – drzbir Nov 24 '16 at 17:45
  • $\begingroup$ 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$. $\endgroup$ – drzbir Nov 24 '16 at 17:59
  • $\begingroup$ You're right, sorry. I'll fix it now. $\endgroup$ – j_random_hacker Nov 24 '16 at 18:00
  • $\begingroup$ 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? $\endgroup$ – drzbir Nov 24 '16 at 19:44
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Nov 25 '16 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.