2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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 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 at 21:39

0

Reset to default

Your Answer

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