7
$\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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 17:24

0

Reset to default

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.