Choosing subsets of a set such that the subsets satisfy a global constraintWe 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 ≤ m ≤ n) such that the average of the p values of the items in I ′ falls within some specified range, [ p l , p u ].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?

Question

Choosing subsets of a set such that the subsets satisfy a global constraintWe 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  ≤  m  ≤  n) such that the average of the   p values of the items in       I    ′   falls within some specified range,   [      p    l    ,      p    u    ].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?

Odin Jacobson · Accepted Answer

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    =      S    m  , for   1  ≤  m  ≤  n.If   m is fixed then the brute force algorithm is   O  (      n    m    ) and so has a polynomial time algorithm.

Choosing subsets of a set such that the subsets satisfy a global constraint We have a set of items

Answered question

Answer & Explanation

New Questions in Precalculus