A fast algorithm for a simple multi-objective minimization?

Question

I have a set $S$ consists of n (arbitrary) integer numbers which I want to partition into $k$ subsets $S_i$ each of size $\frac{n}{k}$ (assume $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.

Answer 1

There is nothing multi-objective about this. Instead you have a pretty standard partitioning problem. I will let other tell us if there is a simple (pseudo-)polynomial solution. I will just give you the naive mixed-integer representation (here implemented in MATLAB using the toolbox YALMIP (developed by me)). The problem is solved in no time using a good MILP solver

m = 50;
k = 10;
n = m*k;
S = ceil(randn(n,1)*20);
A = sum(S)/n;

X = binvar(k,n,'full');    % X(i,j) if S(j) is in set i
T = X*S;                   % Sum of elements in each set
Cost = norm(T - A,1);      % Sum of absolute values
Constraint = [sum(X,1)==1] % Each number in one set only
optimize(Constraint,Cost)