4
$\begingroup$

I have a set of n numbers whose average (arithmetic mean) is x. I have to choose a subset of k numbers from n such that its average is closest to x. Please note that k is the upper bound. If the average can be represented with less than k numbers, then that set is chosen.

For example:
set = {1, 2, 3, 4, 5, 6} (n = 6) (average = 3.5)
If k = 1 then the subset can be either {3} or {4}
If k = 2 then the subset is {3, 4}
If k = 3 then the subset is still {3, 4}

I have to write an algorithm for the same. If this problem is not solvable in polynomial time, what would be a good approach to solve it? Any heuristic approach?

$\endgroup$
  • 3
    $\begingroup$ Your problem should be hard. You can get a good solution by random sampling. $\endgroup$ – Yuval Filmus Dec 24 '15 at 14:03
  • $\begingroup$ Do you know the target average value in advance or is it unknown ? $\endgroup$ – StephenG Dec 25 '15 at 15:18
  • $\begingroup$ The target value is not known in advance $\endgroup$ – user2206344 Dec 28 '15 at 2:37
1
$\begingroup$

I am not sure if you are allowed to use a solver for this, but this problem can be easily formulated as a Mixed Integer Nonlinear Programming (MINLP) problem.

enter image description here

This can be solved with open source solvers like Couenne or Bonmin. Actually this model can be linearized so it can even be solved with linear Mixed Integer Programming (MIP) solvers.

$\endgroup$
  • $\begingroup$ A linearized version of the model can be found here. This version can be solved with any MIP solver. $\endgroup$ – Erwin Kalvelagen Dec 28 '15 at 23:53

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.