1
$\begingroup$

Let $x_1, x_2, \dots, x_n \in \mathbb R$ and $b_1, b_2, \dots, b_n \in \{0,1\}$. I want to know which of all the possible boolean combinations is maximal. For example, if $x_1 = 2$ and $x_2 = -2$,

$$\max \sum_i b_i x_i = 2 \implies b_1 = 1, b_2 = 0$$

I can see that a brute force algorithm will have a running time complexity of $O(2^n)$. My question is whether there is an efficient algorithm for this or, at least, an approximation algorithm.

$\endgroup$
4
$\begingroup$

Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:

  • set $b_i=1$ if $x_i > 0$
  • set $b_i=0$ if $x_i < 0$
  • all others $b_i$ can either be zero or one

It is clear that any other assignment will give you a lower value (either by adding a positive value or not adding a positive one). If $|\{i:x_i=0\}|=K$, then you have $2^K$ solutions. This can be settled in $O(n)$ by a simple linear scanning of $x_i$ values (even less if they are ordered).

$\endgroup$
  • $\begingroup$ It's not that you don't understand something in my question, it's just that I asked it in a very simple way: simpler than my actual problem needs. However, your answer is perfect, so I will try to formulate the right question in another post. Thank you anyway! $\endgroup$ – Cromack Apr 9 '17 at 14:07

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.