Latest update

# $k$-partitioning problem via brute force

2018-03-22 07:26:59

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$?