0
$\begingroup$

I tried to look for some references but could not find any. I knew it is proved to be NP-complete via a transformation from Knapsack or 3DM problem. But I couldn't find a way to apply PCP theorem to get the hardness of approximation for this problem. Thank you.

$\endgroup$
1
$\begingroup$

From the Wikipedia page on the Partition problem: "...there are fully polynomial-time approximation schemes for the subset-sum problem, and hence for the partition problem as well". The references given there are Kellerer, Pferschy, Pisinger and Martello, Toth.

$\endgroup$
  • 2
    $\begingroup$ In fact, every problem that can be solved by a pseudopolynomial algorithm (including partition), that has an integer-valued objective function, and whose objective value is polynomial in unary encoding size has an FPTAS. See Sect. 8.3 in V. Vazirani's Approximation Algorithms. $\endgroup$ – Magnus Lie Hetland Apr 22 '13 at 11:45
  • 3
    $\begingroup$ @Magnus: I think it is the other way - if the integer-valued objective function is polynomial in unary and the problem has an FPTAS, then it has a pseudopoly alg. $\endgroup$ – domotorp Apr 23 '13 at 7:20
  • $\begingroup$ Indeed—that's also what I wrote in the note I linked to above. Got a bit mixed up here. Thanks. $\endgroup$ – Magnus Lie Hetland Apr 30 '13 at 19:36

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.