# A fast algorithm for a simple multi-objective minimization?

I have a set $S$ of $n$ (arbitrary) integers which I want to partition into subsets $S_1, \dots, S_k$, 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.

• "as close as possible" under what metric? Writing $T_i$ for $\sum_{s\in S_i}s$, you can't use $\sum_i (T_i-A)$, since that has value $(n-k)A$ for every partition. $\sum_i |T_i-A|=\sum_i (T_i-A)$ for most partitions of most inputs, since $T_i\approx nA/k\gg A$, so that doesn't help. And if you use something like $\sum_i(T_i-A)^2$, I'd expect that to try to make the partitions as equal as possible, which sounds like it's NP-hard. – David Richerby Feb 21 '15 at 9:09
• @D.W. When you say that something “violates site rules”, please give a reference to the rule in question. In this case, Is cross-posting a question on multiple Stack Exchange sites permitted if the question is on-topic for each site? – Gilles Feb 21 '15 at 12:36
• David, OP is looking for Pareto-optimal solutions, not a single global optimum. I suspect it's still NP-hard to solve exactly though, because it reduces to subset sum for k=2. – jkff Feb 21 '15 at 20:26