2
$\begingroup$

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!

$\endgroup$

migrated from stackoverflow.com Jun 28 '11 at 14:50

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ "which in summation own the largest attributes" - please explain this better. $\endgroup$ – Jacob Jun 28 '11 at 15:24
  • 2
    $\begingroup$ NP-hard wrt which parameter? The number of objects? The problem is unclear -- "serve the maximum when only 2 objects out of the set are allowed to be chosen" how? $\endgroup$ – amit Jun 28 '11 at 16:03
  • $\begingroup$ @kuq, I reworded much of your question (in an edit that has to be approved by someone first before you can see it). Please check to see that my change preserved the intent of your question. $\endgroup$ – Tyson Williams Jun 28 '11 at 16:46
  • 3
    $\begingroup$ Maybe you mean A(a1) + B(a2) + A(a3)? $\endgroup$ – George Jun 28 '11 at 17:27
7
$\begingroup$

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
$\endgroup$
  • $\begingroup$ I don´t know where this line of "code" belongs to. Something like matlab? > max map SubsetsOfSize(N) \S (sum map attributes \A (max map S \e A[e])) If I got you right, my consideration about the np-hardness is right. The 3-Sat is a prove for this or a way to deal with it? I`m sorry but maybe you could explain in a little more detail.. $\endgroup$ – user5751 Jun 28 '11 at 20:33
  • $\begingroup$ In your example, what prevents you from choosing +A, -A, and +B? $\endgroup$ – mhum Jun 28 '11 at 23:46
  • $\begingroup$ It's not optimal. You want the best solution. For example, +A,+B,+C has a score of 29 while +A,-A,+B has a score of only 20. $\endgroup$ – Craig Gidney Jun 29 '11 at 2:14
  • $\begingroup$ @kuq: It's Haskell-like pseudo code. You should use comments for replying to answers, not new answers. $\endgroup$ – Craig Gidney Jun 29 '11 at 2:17
  • $\begingroup$ Ah, I see. That makes sense. You can also do a reduction from Minimum Set Cover. Each column is an element of the ground set, each row is a subset, each entry is 1 or 0 depending if that subset contains that ground element. $\endgroup$ – mhum Jun 29 '11 at 4:28
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The fact that the problem can be formulated as a 0-1 integer linear program does not imply its NP-hardness. $\endgroup$ – Marcus Ritt Jun 28 '11 at 19:36
  • $\begingroup$ @Marcus: so you are essentially unconvinced that my formulation of this problem as a integer linear programming is an "if and only if" equivalent formulation. I think I can claim that if you find a solution to my problem then that solution works for the original problem, and if you find a solution of the original problem then it is a solution of my problem, which would solve your concern. $\endgroup$ – ldog Jun 28 '11 at 20:19
  • $\begingroup$ That is not how NP reductions work. To show that kuq's problem is NP-complete you would need to show that an arbitrary instance of, say, integer programming can be formulated as an instance of kuq's problem. Instead, you've shown that an instance of kuq's problem can be formulated as an integer program. $\endgroup$ – mhum Jun 28 '11 at 21:30
  • $\begingroup$ Ahh yea thats right, since the problem $\text{maximize } 1$ is an instance of a binary integer programming problem but clearly is trivial to solve. I have not proved it, but if Strilanc's reduction holds then this shows an approach on how to solve this problem practically with a ILP solver $\endgroup$ – ldog Jun 28 '11 at 22:42

Your Answer

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