Complexity of a weighted subset selection problem.

Question

I'm currently thinking about a problem I'd like to manage in one of my applications.

There is a set of objects $\{A, B, C, D, \ldots\}$. Every object has the same attributes with different values. For example, $A$'s attribute $a_1$ has the value $A(a_1)$, $B$'s attribute $a_1$ has the value $B(a_1)$ and so on.

Now I want to pass a number $x$ which represents the maximum number of objects to selected from the set. For example, $x = 2$ would mean that any combination of at most 2 objects are allowed to be selected from the set.

Given this table of attributes and the number $x$, the algorithm should return at most $x$ objects which, in summation, own the largest attributes. Only the greater one counts.

For example: $A,B,C$ with attributes $a_1,a_2,a_3$ and $x = 2$:

$\begin{array}{|c|c|c|c|} & a_1 & a_2 & a_3\\\hline A & 1 & -100 & -1\\\hline B & -2 & 2 & -200\\\hline C & -20 & -10 & 10\\\hline \end{array}$

The algorithm should return $A$ and $B$ since $A(a_1) + A(a_2) + B(a_3)$ serve the maximum when at most 2 objects from the set are allowed to be selected.

If I'd use brute-force, I simply would test all $\binom{n}{x}$ combinations and calculate the overall sum.

Is there a faster way to do this?

Thanks!

Answer 1

I'm going to assume your problem is equivalent to what this computes:

max map SubsetsOfSize(N) \S (sum map attributes \A (max map S \e A[e]))

In other words, find the best set of items such that picking the best available item attribute values gives the largest sum.

Yes, it's NP-Complete. You can encode 3-Sat into it. Each variable becomes a true-row and false-row. Each clause becomes a column with a 1 in the rows corresponding to its satisfying assignments. You prevent true-row and false-rows from being selected simultaneously by adding columns with huge values in those two rows (0 everywhere else) and requiring that exactly half the rows be selected (thus the optimal solution will require each huge value, and picking a true and false will lose a huge value somewhere else). The 3-sat instance being satisfiable is equivalent to being able to select items for a total score of HugeValue*NumVariables + NumClauses.

Example transformation:

(A or B or C) and (not A or B or not C)

   uA uB uC  C1 C2
+A  9  0  0  1  0
-A  9  0  0  0  1
+B  0  9  0  1  1
-B  0  9  0  0  0
+C  0  0  9  1  0
-C  0  0  9  0  1
N = 3

Answer 2

If you rewrite this as the (I think) equivalent problem

$$ \begin{eqnarray} \text{maximize } \sum _j \sum _i x_{i j}A_i(a_j) \end{eqnarray} $$ $\text{subject to:}$ $$\sum_j x_{i j} \le x$$ $$\sum_i x_{i j} = 1 $$ $$x_{i j} \in \left\{0,1\right\}$$

this is a linear integer programming problem. In fact, I think all the variables are binary. This shows that your problem is an instance of BILP (Binary Integer Linear Programming) but doesn't prove it is NP-hard or complete.

Luckily, this of course means you can use any of the awesome integer programming libraries out there to try to find an answer with minimal work from your part.

Also, I'd just like to note that if the parameter $x$ is fixed then $\binom{n}{x}\in O(n^x)$ which makes the brute force polynomial time.

Hopefully, I've given you a possible answer to your question "Is there a faster way to do this?"

If you are more interested in the proof of NP-completeness see the other answer's reduction.

PS. Does anyone know how to do an equation array in this latex? I can't seem to get \\ to work