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

Question

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?

• Raphael: If this does not get a good answer after a few days, it's a candidate for migration to Theoretical Computer Science.
• user742: @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.
• RDN: 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.
• user742: @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).
• Raphael: @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)$.

Answer 1

If you find a fast (sub-exponential) exact algorithm for 3-Partition , while 3-Partition is NP-Complete, then dear sir you have just proven P=NP, which no body has done so far, and you have a 1M $ price waiting for you as well as wealth and fame, cheers.

Anyway if you do have a faster than a SAT solver, wouldn't you actually be performing SAT it's self faster? I mean if you can reduce SAT to 3-PARTITION and you can solve 3-PARTITION in sub-expo time, doesn't that mean that SAT can be solved in sub-expo time, hence all NP-COMPLETE problems also can be solved in such time? So you might as well be looking for a sub-expo time solution of any other NP-COMPLETE problem just as well, it would still be a significant breakthrough.

• xskxzr: Sub-exponential does not mean polynomial.
• greybeard: @xskxzr: as has been commented almost five years ago.