I have an algorithm problem which I do not know how to solve and I think it is NP-complete. Let me try to explain with a general example.

Given $n$ objects, each with $k$ possible properties, oversample (with replacement) among the $n$ objects to achieve a desired proportion of objects with specific properties and sample each of the $n$ objects at least once. Note that each object can have several properties. Therefore, if you sample an object with multiple properties, multiple proportions will be affected (and of course all proportions will be affected).

Specific example: a bag contains 6 objects, each with 3 possible properties: color (e.g. blue), shape (e.g. Cube), and temperature (e.g. cold).

  • Object 1: Blue
  • Object 2: Blue
  • Object 3: Blue, Cube
  • Object 4: Blue
  • Object 5: Blue, Cold
  • Object 6: Blue, Cube, Cold

The current proportions are: 100 % blue, 33 % cube, 33 % cold.

The goal is to specify a desired proportion, like: 100 % blue, 50 % cube and 33 % cold. To achieve this I can sample Object 3 and Object 6 to get 100 % blue, 50 % cube and 37.5 % cold or sample Object 3 twice to get 100 % blue, 50 % cube and 25 % cold. Both solutions are accepted, I just want an approximate.

Is there an algorithm or approximation algorithm to do this?

  • $\begingroup$ The term NP-complete is for decision problems, i.e., problems that produce a Boolean output. How is this a decision problem? $\endgroup$ Nov 13 '21 at 8:55
  • $\begingroup$ Why don't you produce a minimal mathematical model? At least define the sets of colors, shapes and temperatures. $\endgroup$ Nov 13 '21 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.