0
$\begingroup$

Anyone know if an optimization variant of the 3-partition problem (as explained there) would also be strongly np-complete?

This would be where the goal is to group a multiset whose size is evenly divisible by 3 into triplets that sum to as close to a target as possible and to produce this grouping. This would not be a decision problem but an actual optimization problem.

$\endgroup$
3
$\begingroup$

The objective function $f$ (to minimize) is not completely formalized in the question. It is written that the groups should "sum to as close to a target as possible", so it seems natural to assume that $f$ is $0$ if the sum of the elements in each group is equal to the target, and greater than $0$ otherwise.

Two examples of such functions are the maximum and the sum of the absolute differences between the sum of the elements in each group and the target.

Under this assumptions, the above optimization problem is strongly NP-hard since the answer to the decision problem is "yes" if and only if an optimal solution $S$ to the optimization problem satisfies $f(S)=0$.

It would not be NP-complete since it does not belong to NP (which only contains decision problems).

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.