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

Lovellss 2022-06-24 Answered
Choosing subsets of a set such that the subsets satisfy a global constraint
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 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?
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

Odin Jacobson
Answered 2022-06-25 Author has 17 answers
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.

We have step-by-step solutions for your answer!

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-09-09
In a fuel economy study, each of 3 race cars is tested using 5 different brands of gasoline at 7 test sites located in different regions of the country. If 2 drivers are used in the study, and test runs are made once under each distinct set of conditions, how many test runs are needed?
asked 2021-09-08
A restaurant offers a $12 dinner special that has 7 choices for an appetizer, 12 choices for an entree, and 6 choices for a dessert. How many different meals are available when you select an appetizer, an entree,and a dessert?
asked 2022-06-14
A bus follows its route through nine stations, and contains six passengers. What is the probability that no two passengers will get off at the same station?
asked 2021-11-13
A student is getting ready to take an important oral examination and is concerned about the possibility of having an “on” day or an “off” day. He figures that if he has an on day, then each of his examiners will pass him, independently of each other, with probability .8, whereas if he has an off day, this probability will be reduced to .4. Suppose that the student will pass the examination if a majority of the examiners pass him. If the student feels that he is twice as likely to have an off day as he is to have an on day, should he request an examination with 3 examiners or with 5 examiners?
asked 2022-09-23
Why is k = 1 n k m a polynomial with degree m + 1 in n?
asked 2022-06-04
Let us suppose to have a set of N elements and to choose m elements out of the set. I know I can do it in ( N m ) ways; but I want to know how many of these combinations contain k predefined elements (say 1 , 2 , . . . , k).
asked 2022-07-01
Let's call S the infinite string that is made by concatenating the consecutive positive integers written down in base 10. Thus,
S = 12345678910111213141516171819202122232425
Any number in S occurs multiple times. The first occurrence of 3 is in the third position of the series, the second occurrence is in the seventeenth position, and so on.
How do I find the position of the hundredth occurrence of 3? Is there a pattern?

New questions