We have a set of items $I = \{i_1, i_2, ..., i_n\}$. Each of these items has what we call a p value, which is some real number. We want to choose a subset of $I$, call it $I'$, of size $m$ (for some $m$ with $1 \le m \le n$) such that the average of the p values of the items in $I'$ falls within some specified range, $[p_l, p_u]$. (For example, we might require an average p value between 0.70 and 0.74.) Moreover, we want to do this efficiently.

We hope to do this in O(n) time, but any polynomial time algorithm is good enough. We certainly do not want to just try every possible subset of I of size $m$ and then check whether it satisfies the average p-value constraint.

Finally, we will be doing this repeatedly and we want the subsets chosen to be a uniformly random distribution over all the possible such subsets.

Is there a way of doing this?


1 Answer 1


From my answer at math.stackexchange: https://math.stackexchange.com/questions/3205/choosing-subsets-of-a-set-such-that-the-subsets-satisfy-a-global-constraint/3207#3207

Assuming $m$ is an input, your problem is NP-Complete.

Subset sum can be reduced to it.

Given $A = \\{x_{1}, ..., x_{n}\\}$ for which we need to find a subset of sum $S$, we can create $n$ inputs to your algorithm, with input $A$, $m$ and $p_{L} = p_{U} = \frac{S}{m}$, for $1 \leq m \leq n$.

If $m$ is fixed then the brute force algorithm (which you don't want) is $O(n^m)$ and so has a polynomial time algorithm.

If this does not answer your question, can you please clarify exactly what you need?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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