# Fastest known algorithm for $3$-$\mathrm{Partition}$ problem

$$3$$-$$\mathrm{Partition}$$ problem is $$\mathsf{NP}$$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $$\mathsf{P=NP}$$. I am looking for the fastest known exact algorithm that solves $$3$$-$$\mathrm{Partition}$$.

Is there a fast (e.g subexponential) algorithm for $$3$$-$$\mathrm{Partition}$$? Is it possible to solve it faster than using SAT solvers?

• If this does not get a good answer after a few days, it's a candidate for migration to Theoretical Computer Science. – Raphael Mar 26 '13 at 13:01
• @Raphael, Yes I agree, but I didn't search enough but by my knowledge I couldn't find anything, so I said it's better to first ask it here. – user742 Mar 26 '13 at 13:23
• Clearly you need to go with an approximation algorithm and it will have to be at best a PTAS (if that is achievable). I have not come across any specific approximations for 3-partition, but if you would like to construct your own, there are a couple of standard tricks you could use to construct it (works for any kind of approximation) -- (1) Take the DP solution and approximate the state-space down to some polynomial size, or (2) Perform input rounding so that the inputs produce a polynomial size state-space, or (3) a combination of (1) and (2). It would be cool to see what bounds you get. – RDN Mar 26 '13 at 19:32
• @RDN, First I'm not looking for apprximation, approximation is another problem, second, I cannot see how DP is helpful, I strongly mentioned this is strong NP-Compelete, I don't think you could find any good DP for this (except converting to bin packing and allowing 3 item per bin, which is not really DP). – user742 Mar 27 '13 at 9:16
• @RDN Note that "subexponential" is not (strictly) the same as "polynomial", see here. I guess Saeed would also be interested in an algorithm that runs in time, say, $O(1.1^n)$. – Raphael Mar 27 '13 at 12:09