2
$\begingroup$

I have some constant vector $\mathbf{s}$ on $n$ dimensions, where every element of $\mathbf{s}$ is a real number, and I would like to multiply it by every possible $n$-dimensional binary vector $\mathbf{v}_j\ (0\leq j < 2^n)$.

I only care about whether $\mathbf{s}\cdot \mathbf{v}_j > 0$. I would like to count all of the times this condition holds.

Question: As the naive algorithm has complexity $O(2^n)$, it blows up fast. What are my options for optimizing this for large $n$?

$\endgroup$
  • 1
    $\begingroup$ So, you basically want to know how many subsets of $\mathbf{s}$ sum to a positive value? $\endgroup$ – ryan Apr 1 at 22:53
  • $\begingroup$ You want to determine the expected value of a linear threshold function (LTF). There is some literature on that. $\endgroup$ – Yuval Filmus Apr 2 at 4:20
  • $\begingroup$ You can use a meet-in-the-middle approach to get an $O(2^{n/2})$ algorithm: calculate all sums of each half of the vector, then run a two pointer algorithm. $\endgroup$ – Yuval Filmus Apr 2 at 4:22
  • $\begingroup$ Additionally, if the real numbers can be expressed as rationals with some small common denominator, expressing it as a knapsack problem will help. If it is acceptable to round to such numbers (e.g., to three digits after the decimal point), the same applies. $\endgroup$ – Gassa Apr 2 at 11:03
  • $\begingroup$ @ryan Thanks for reformulating -- that is correct. $\endgroup$ – Jake Brukhman Apr 2 at 14:53
3
$\begingroup$

Suppose that you could solve this in $T(n)$. Given a list of positive integers $a_1,\ldots,a_n$ and a target $T$, consider the two instances $a_1,\ldots,a_n,-T$ and $a_1,\ldots,a_n,-T+1$. Denoting by $N(\cdots)$ the number of positive sums, we get:

  • $N(a_1,\ldots,a_n,-T)$ is the number of subsets of $\{a_1,\ldots,a_n\}$ whose sum is larger than $T$.
  • $N(a_1,\ldots,a_n,-T+1)$ is the number of subsets of $\{a_1,\ldots,a_n\}$ whose sum is at least $T$.

By comparing these two numbers, you can solve SUBSET-SUM in time $T(n+1)$.

(There are some potential differences in the computation models, that I leave you to ponder.)

There is a simple $O(2^{n/2})$ algorithm, which proceeds as follows. We break the array $s_1,\ldots,s_n$ into two equal halves. We compute an ordered list $A_1,\ldots,A_{2^{n/2}}$ of all sums of the first half, and an ordered list $B_1,\ldots,B_{2^{n/2}}$ of all sums of the second half. This takes time $O(2^{n/2})$ if done carefully (by iterative merging). We put a pointer $j$ at $B_{2^{n/2}}$, and decrease it until $A_1 + B_j \le 0$. The value of $j$ tells us the number of pairs $(1,j')$ satisfying $A_1 + B_j > 0$. Then we do the same for $A_2$ — note that we can start the scan at the current value of $j$; and so on. This phase also takes $O(2^{n/2})$.

$\endgroup$

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.