<p>Let <span class="math-container">$S$</span> be a set of <span class="math-container">$n$</span> positive integers, and <span class="math-container">$p$</span> be a partition of <span class="math-container">$S$</span> into <span class="math-container">$m$</span> mutually disjoint subsets, such that no subset contains more than <span class="math-container">$k$</span> elements.</p>
<ul>
<li>Let <span class="math-container">$\mathcal{P}$</span> denote the set of all partitions <span class="math-container">$p$</span>.</li>
<li>Let <span class="math-container">$sum\{A\}$</span> denote the sum of all elements of the integer-set <span class="math-container">$A$</span>.</li>
</ul>
<p>Problem: Given <span class="math-container">$S$</span>, <span class="math-container">$m$</span> and <span class="math-container">$k$</span>, determine: <span class="math-container">$min_{p\in\mathcal{P}}\{max\{sum(A)|A\in p\}\}.$</span></p>
<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.</p>

CC BY-SA 4.0
2023-03-29T10:10:48.027Z
It's a variation of the optimization version of the partition problem: https://en.wikipedia.org/wiki/Partition_problem.
Yixin Cao
CC BY-SA 4.0
2023-03-30T21:39:26.643Z
Specifically when $m=2$ and $k=n$ this is the optimization version of the (NP-hard) partition problem.
Neal Young
<permutations><partition-problem><combinatorics><subset-sum>
Partition of a set of integers into subsets where the max. of the subset-sums is minimum
Code-searcher
# Partition of a set of integers into subsets where the max. of the subset-sums is minimum

(Asked by: username_0 on 2023-03-29)

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.

**Tags:** permutations, partition-problem, combinatorics, subset-sum

> **Comments:**
> **username_1**: It's a variation of the optimization version of the partition problem: https://en.wikipedia.org/wiki/Partition_problem.  
> **username_2**: Specifically when $m=2$ and $k=n$ this is the optimization version of the (NP-hard) partition problem.  

---

## 0 answers

