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?

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

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ A linearized version of the model can be found here. This version can be solved with any MIP solver. $\endgroup$
    – Erwin Kalvelagen
    Commented Dec 28, 2015 at 23:53

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.