<p>The 3-partition as defined <a href="http://en.wikipedia.org/wiki/3-partition_problem" rel="nofollow">here</a> 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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-03-12T15:09:36.493Z
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
CC BY-SA 3.0
2012-03-12T15:24:04.600Z
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
CC BY-SA 3.0
2012-03-12T15:45:24.653Z
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
CC BY-SA 3.0
2012-03-12T15:47:01.937Z
@TsuyoshiIto actually, what prevents the argument you give from working for any approximation as well, like $O(log m)$?
aelguindy
CC BY-SA 3.0
2012-03-12T15:48:40.670Z
Nothing.  See my second comment. :)
Tsuyoshi Ito
CC BY-SA 3.0
2012-03-12T15:49:31.137Z
@TsuyoshiIto again realized that a bit late :-). So the answer turns out to be quite easy. You could turn your comment to an answer and I'll accept it. Thanks!
aelguindy
CC BY-SA 3.0
2012-03-12T17:24:45.403Z
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
CC BY-SA 3.0
2012-03-12T17:44:54.567Z
@SureshVenkat mm.. That sounds reasonable except that I wanted the values to play a role in the cost function.. Can it be fixed in such a way that $s(.)$ is involved?
aelguindy
CC BY-SA 3.0
2012-03-12T19:40:24.813Z
Sure. maximize $\sum s(S_k)$
Suresh Venkat
CC BY-SA 3.0
2012-03-12T22:10:06.047Z
@SureshVenkat That was the first thing I looked at, but somehow I convinced myself that it has the same problem as minimizing the original objective function.
aelguindy
CC BY-SA 3.0
2012-03-13T00:48:47.363Z
Well for the exact answer it is. For approximations it isn't.
Suresh Venkat
<cc.complexity-theory><ds.algorithms><approximation-algorithms><approximation-hardness><partition-problem>
Approximation results for 3-partition
aelguindy
# Approximation results for 3-partition

(Asked by: username_0 on 2012-03-12)

The 3-partition as defined [here](http://en.wikipedia.org/wiki/3-partition_problem) 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?~~

**Tags:** cc.complexity-theory, ds.algorithms, approximation-algorithms, approximation-hardness, partition-problem

> **Comments:**
> **username_1**: 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.  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: @TsuyoshiIto actually, what prevents the argument you give from working for any approximation as well, like $O(log m)$?  
> **username_1**: Nothing.  See my second comment. :)  
> **username_0**: @TsuyoshiIto again realized that a bit late :-). So the answer turns out to be quite easy. You could turn your comment to an answer and I'll accept it. Thanks!  
> **username_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.  
> **username_0**: @SureshVenkat mm.. That sounds reasonable except that I wanted the values to play a role in the cost function.. Can it be fixed in such a way that $s(.)$ is involved?  
> **username_2**: Sure. maximize $\sum s(S_k)$  
> **username_0**: @SureshVenkat That was the first thing I looked at, but somehow I convinced myself that it has the same problem as minimizing the original objective function.  
> **username_2**: Well for the exact answer it is. For approximations it isn't.  

---

## 0 answers

