Is the following special case of multiway number partitioning NP-hard? - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-26T16:48:28Z https://cstheory.stackexchange.com/feeds/question/50975 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/50975 1 Is the following special case of multiway number partitioning NP-hard? Ryoshun Oba https://cstheory.stackexchange.com/users/65550 2022-01-13T16:49:32Z 2022-01-13T16:49:32Z <p>The following problem is a decision problem of <em>multiway number partitioning</em> (<a href="https://en.wikipedia.org/wiki/Multiway_number_partitioning#:%7E:text=In%20computer%20science%2C%20multiway%20number,the%20Identical%2Dmachines%20scheduling%20problem." rel="nofollow noreferrer">wikipedia</a>) (Note that <span class="math-container">$k$</span> is also a part of an input in the following problem, while <span class="math-container">$k$</span> is a fixed number in wikipedia definition).</p> <blockquote> <p>Given <span class="math-container">$k, n \in \mathbb{N}$</span> and <span class="math-container">$n$</span> numbers <span class="math-container">$a_1, \ldots, a_n \in \mathbb{Z}$</span>, decide if there exists a partition of the numbers into <span class="math-container">$k$</span> parts so that the sum of numbers in each part equals <span class="math-container">$\frac{\sum a_i}{k}$</span>.</p> </blockquote> <p>As this problem includes the <a href="https://en.wikipedia.org/wiki/Partition_problem" rel="nofollow noreferrer">partition problem</a> as its special case (i.e. <span class="math-container">$k=2$</span>), multiway number partitioning is NP-hard.</p> <p>I would like to know whether the hardness still holds for the following special case of multiway number partitioning (The only difference is that we assume each number is <span class="math-container">$0$</span> or <span class="math-container">$1$</span>).</p> <blockquote> <p>Given <span class="math-container">$k, n \in \mathbb{N}$</span> and <span class="math-container">$n$</span> numbers <span class="math-container">$a_1, \ldots, a_n \in \{0,1\}$</span>, decide if there exists a partition of the numbers into <span class="math-container">$k$</span> parts so that the sum of numbers in each part equals <span class="math-container">$\frac{\sum a_i}{k}$</span>.</p> </blockquote> <p>In this special case, when <span class="math-container">$k$</span> or <span class="math-container">$n-k$</span> is a fixed constant, it is easy to see that the problem is polynomial-time solvable. This is because if <span class="math-container">$k$</span> is a constant, you can use dynamic programming and if <span class="math-container">$n-k$</span> is a constant, the number of possible partitions is at most the polynomial of <span class="math-container">$n$</span>, hence you can check the condition directly.</p> <p>As there seems to be no efficient algorithm for middle size <span class="math-container">$k$</span>, I conjecture that multiway number partitioning for this special case is still NP-hard.</p> <p>I would like to know if anybody knows about this.</p>