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

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

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.