Let $S$ be a set of $n$ positive integers, and $p$ be a partition of $S$ into $m$ mutually disjoint subsets, such that no subset contains more than $k$ elements.

  • Let $\mathcal{P}$ denote the set of all partitions $p$.
  • Let $sum\{A\}$ denote the sum of all elements of the integer-set $A$.

Problem: Given $S$, $m$ and $k$, determine: $min_{p\in\mathcal{P}}\{max\{sum(A)|A\in p\}\}.$

I tend to believe that the above problem has a very strong similarity with the knapsack problem, and therefore, is unlikely to have a poly-time solution.

  • 1
    $\begingroup$ It's a variation of the optimization version of the partition problem: en.wikipedia.org/wiki/Partition_problem. $\endgroup$
    – Yixin Cao
    Mar 29, 2023 at 10:10
  • 1
    $\begingroup$ Specifically when $m=2$ and $k=n$ this is the optimization version of the (NP-hard) partition problem. $\endgroup$
    – Neal Young
    Mar 30, 2023 at 21:39


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.