Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
3  
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
4  
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
2  
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
show 6 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.