1
$\begingroup$

The following problem is a decision problem of multiway number partitioning (wikipedia) (Note that $k$ is also a part of an input in the following problem, while $k$ is a fixed number in wikipedia definition).

Given $k, n \in \mathbb{N}$ and $n$ numbers $a_1, \ldots, a_n \in \mathbb{Z}$, decide if there exists a partition of the numbers into $k$ parts so that the sum of numbers in each part equals $\frac{\sum a_i}{k}$.

As this problem includes the partition problem as its special case (i.e. $k=2$), multiway number partitioning is NP-hard.

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 $0$ or $1$).

Given $k, n \in \mathbb{N}$ and $n$ numbers $a_1, \ldots, a_n \in \{0,1\}$, decide if there exists a partition of the numbers into $k$ parts so that the sum of numbers in each part equals $\frac{\sum a_i}{k}$.

In this special case, when $k$ or $n-k$ is a fixed constant, it is easy to see that the problem is polynomial-time solvable. This is because if $k$ is a constant, you can use dynamic programming and if $n-k$ is a constant, the number of possible partitions is at most the polynomial of $n$, hence you can check the condition directly.

As there seems to be no efficient algorithm for middle size $k$, I conjecture that multiway number partitioning for this special case is still NP-hard.

I would like to know if anybody knows about this.

$\endgroup$
4
  • 2
    $\begingroup$ Since all input numbers are $0$ or $1$, such a partition exists if and only if $(\sum a_i)/k$ is an integer. This is trivial to check in polynomial time. $\endgroup$
    – Gamow
    Jan 13 at 17:02
  • $\begingroup$ Nice first question! Welcome to our community! $\endgroup$ Jan 14 at 0:10
  • $\begingroup$ To extend @Gamow's observation, the straightforward dynamic program for a problem with element universe $U = \{0,1,...,u\}$ has running time $O(nku^{k-1})$. When $u=1$, the only truly expensive part of the algorithm drops out. $\endgroup$
    – Yonatan N
    Jan 14 at 4:21
  • $\begingroup$ Thank you so much for the solultion. I should have come with that. $\endgroup$ Jan 14 at 6:59

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.