2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – David Richerby Feb 21 '15 at 9:09
  • 1
    $\begingroup$ @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? $\endgroup$ – Gilles Feb 21 '15 at 12:36
  • $\begingroup$ 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. $\endgroup$ – jkff Feb 21 '15 at 20:26

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.