1
$\begingroup$

Given a multiset of numbers $X = \{x_1, \dots, x_n\}$, such that $\sum X = 0$, how can $X$ be partitioned to the maximum number of subsets so that each subset sums to zero?

I have searched around a lot, but none of the partition or packing problem variants seem to address this particular case.

$\endgroup$
2
  • $\begingroup$ What exactly is your question? Looking for algorithms? Hardness proofs? References? $\endgroup$ Commented Feb 6, 2016 at 17:31
  • $\begingroup$ I'm looking for an algorithm, yes. I have an implementation of the dynamic programming solution, which I can use to find some subsets, but I don't know how to continue from there on, or if i'm on the right track at all. $\endgroup$
    – mgunyho
    Commented Feb 6, 2016 at 17:47

1 Answer 1

5
$\begingroup$

3-Partition reduces to this problem, so it's strongly $NP$-hard. Moreover, 4-Partition also reduces to it (and the blowup is linear), so assuming the exponential time hypothesis there's no $2^{o(n)}$ algorithm.

Using dynamic programming there's a $O^*(4^n)$ algorithm, it would be interesting if you could do $2^n$ or even $1.99^n$.

$\endgroup$
2
  • 1
    $\begingroup$ Can you specify the algorithm? $\endgroup$
    – mgunyho
    Commented Feb 6, 2016 at 17:48
  • $\begingroup$ @mgunyho Here is the actual reduction to the 3-partition problem I think :) $\endgroup$
    – iago-lito
    Commented Aug 26, 2018 at 7:04

Your Answer

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

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