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.
A fast algorithm for a simple multi-objective minimization?
algorithms;optimization;complexity