<p>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
<a href="http://books.google.com/?id=u5DB7gck08YC&amp;pg=PA97" rel="nofollow">Kellerer, Pferschy, Pisinger</a> and <a href="http://www.ams.org/mathscinet-getitem?mr=1086874" rel="nofollow">Martello, Toth</a>. </p>

CC BY-SA 3.0
2013-04-22T11:45:46.453Z
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](http://www.idi.ntnu.no/~mlh/algkon/complexity.pdf). See Sect. 8.3 in V. Vazirani's *Approximation Algorithms*.
Magnus Lie Hetland
CC BY-SA 3.0
2013-04-23T07:20:00.503Z
@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.
domotorp
CC BY-SA 3.0
2013-04-30T19:36:24.960Z
Indeed—that's also what I wrote in the note I linked to above. Got a bit mixed up here. Thanks.
Magnus Lie Hetland
CC BY-SA 3.0
2013-04-22T03:56:14.583Z
2013-04-22T03:56:14.583Z
Thomas Kalinowski
<p>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.</p>

<np-hardness>
Is there any reference on the hardness of approximation for 2-partition problem?
Qiao
# Is there any reference on the hardness of approximation for 2-partition problem?

(Asked by: username_0 on 2013-04-22)

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.

**Tags:** np-hardness


---

## 1 answers

### Answer by username_1 on 2013-04-22. Score: 1

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](http://books.google.com/?id=u5DB7gck08YC&pg=PA97) and [Martello, Toth](http://www.ams.org/mathscinet-getitem?mr=1086874).

> **Comments:**
> **username_2**: 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](http://www.idi.ntnu.no/~mlh/algkon/complexity.pdf). See Sect. 8.3 in V. Vazirani's *Approximation Algorithms*.  
> **username_3**: @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.  
> **username_2**: Indeed—that's also what I wrote in the note I linked to above. Got a bit mixed up here. Thanks.  

---

