1

I have a set of n (arbitrary) integer numbers S which I want to partition into k subsets S_i each of size n/k (you can assume that k divides n). Let A be the arithmetic mean of elements of the set S. I am looking for the fastest algorithm that fills each S_i with elements of S such that sum of the elements of each S_i is as close as possible to A. Essentially, this is a multi-objective minimization problem and I am looking for Pareto minimal solutions. The complexity of the brute-force algorithm is O(n!). I am wondering if there exists a faster algorithm.

  • 2
    I'm voting to close this question as off-topic because it's about findind a very specific computacional algorithm, I think it would be best suited for cstheory.stackexchange.com – Tulains Córdova Feb 21 '15 at 4:56
  • 3
    Come on, guys, this site here is about algorithms for specific tasks, and it is not clear the OP needs an answer on research-level depth (which would be required to qualify for "cstheory"). – Doc Brown Feb 21 '15 at 8:07
  • Can you please elaborate on what you mean by "Pareto minimum"? Does that mean you are not necessary looking for a global optimum, but just for "good" solutions which are local minima? – Doc Brown Feb 21 '15 at 8:09
  • I think this is very similar to the bin packing problem, which is NP-hard. Maybe you can find inspiration in the approximate algorithms that exist for it. – Davidmh Feb 21 '15 at 15:29
  • This is not CS theory, according to the definition at that site. They define theoretical CS as those problems without known, obvious solutions. You might try the CS only site though. – Frank Hileman Feb 23 '15 at 18:41

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.