6
$\begingroup$

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?

Improve this question
$\endgroup$
11
  • 3
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 12 '12 at 15:09
  • $\begingroup$ 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. $\endgroup$ – aelguindy Mar 12 '12 at 15:24
  • 4
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Mar 12 '12 at 15:45
  • $\begingroup$ @TsuyoshiIto actually, what prevents the argument you give from working for any approximation as well, like $O(log m)$? $\endgroup$ – aelguindy Mar 12 '12 at 15:47
  • 2
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Mar 12 '12 at 17:24

Your Answer

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

Browse other questions tagged or ask your own question.