Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The 3-partition as defined here is a strongly NP-complete decision problem. Consider one optimization problem of 3-partition where the $m$ subsets each have at most three elements and a sum of not more than $B$ The goal is to minimize $s(S) - \sum_{k=1}^{m} s(S_k)$, i.e. the total value of leftover elements.

This is obviously strongly NP-complete as well. I am asking if anyone is aware of approximation/inapproximability results (other than the obvious nonexistence of FPTAS). I tried searching, but maybe I am not using the correct keywords.

EDIT: As pointed out in the comment below, there is no constant-factor approximation. Are there any (non-constant) approximation results?

share|cite|improve this question
If the objective is to minimize the total value of leftover elements, then any constant-factor approximation is NP-hard for a trivial reason (distinguishing 0 from nonzero is equivalent to the decision version of 3-partition, which is NP-complete). Maybe you want to use a different objective function. – Tsuyoshi Ito Mar 12 '12 at 15:09
Good point, I arrived at that shortly before your comment, I am still a bit slow at these realizations. I'll modify the question asking for other results. – aelguindy Mar 12 '12 at 15:24
In fact, whether it is a constant-factor approximation or not is not important. Even a non-constant-factor approximation implies P=NP; if you want to use your objective function, you cannot hope for a multiplicative approximation at all (unless you prove P=NP at the same time). One way to work around this is to consider additive approximation, but it seems easier to me to consider multiplicative approximation under a different objective function. – Tsuyoshi Ito Mar 12 '12 at 15:45
@TsuyoshiIto actually, what prevents the argument you give from working for any approximation as well, like $O(log m)$? – aelguindy Mar 12 '12 at 15:47
One way to "fix" the formulation is to instead maximize the number of "covered" elements. This is the more natural generalization of 2-partition, which is just matching. Then the approximation questions are well founded. – Suresh Venkat Mar 12 '12 at 17:24

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.