# $k$-partitioning problem via brute force

Given a set of non-negative integers $A = \{a_1,a_2,\dots,a_N \}$, the $k$-partitioning problem is to partition the numbers into $k$ sets $\{A_1,A_2,\dots, A_k\}$ such that the deviation: $$\underset{j,k}{\text{max }} \left|\sum_{a_i \in A_j} a_i - \sum_{a_i \in A_k} a_i \right|$$ is minimized. Is there any non-trivial upper bound that can be formulated for the minimum deviation that $A$ admits (this would not be computable as the decision problem is in NP)? Possibly in terms of $\underset{a \in A}{\text{max }} a$?

• This seems more appropriate on Math.SE. – xskxzr Mar 22 '18 at 9:42
• @D.W. I was looking to find an upper bound as stated in the question. – Television Mar 22 '18 at 19:55