7
$\begingroup$

$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?

Improve this question
$\endgroup$
10
  • $\begingroup$ If this does not get a good answer after a few days, it's a candidate for migration to Theoretical Computer Science. $\endgroup$
    – Raphael ♦
    Mar 26 '13 at 13:01
  • 1
    $\begingroup$ @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. $\endgroup$
    – user742
    Mar 26 '13 at 13:23
  • $\begingroup$ 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. $\endgroup$
    – RDN
    Mar 26 '13 at 19:32
  • 1
    $\begingroup$ @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). $\endgroup$
    – user742
    Mar 27 '13 at 9:16
  • 1
    $\begingroup$ @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)$. $\endgroup$
    – Raphael ♦
    Mar 27 '13 at 12:09
-1
$\begingroup$

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.

Improve this answer
$\endgroup$
2

Your Answer

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