I've been thinking about a division problem for groups that I haven't found a dynamic programming solution and I'm trying to analyze the complexity of the problem.

There is a set of $n$ positive numbers ($S$), a vector of group sizes (let's call it $Sizes$), and a parameter $Y$. Find a way for divide the $n$ numbers into groups that their size describes in $Sizes$ s.t. the $constraint$ in close as possible to $Y$.

For example, $ S = \{1,1,2,2,3,4,4,7,9,11\}$, $Sizes = [2,2,3,3]$, $Y=2$ and $constraint =$ the variance of the group. Of course that the $constraint$ could be changed in other cases. But this is representative example.

Has this problem any dynamic programming solution? or that the complexity is exponential (which means $NP$ problem)?

Which approximation approaches can help me in this case?

Thanks in advance!

  • $\begingroup$ I don't know what "their size describes in S s.t. the constraint in close as possible to Y" means. Can you please describe your problem more clearly? Can you describe the context in which you encountered this task? Can you credit the original source? Have you followed the systematic process in cs.stackexchange.com/tags/dynamic-programming/info, and can you show us what progress you've made so far? $\endgroup$ – D.W. Jun 25 '20 at 7:11

The difficulty of your problem heavily depends on "constraint".

For example if $n=3k$, $\text{size}=[\underbrace{3,3,3,...}_{k\text{ times}}]$, and the constraint is that the sum of the numbers each group must be equal, then your problem is strongly NP-hard since it is exactly $3$-partition.

The same problem with groups of size $2$ is polynomial.

Notice that both problems are in $\mathsf{NP}$ and that being in $\mathsf{NP}$ does not mean that the complexity to solve it is exponential.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.