Return to Answer

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 sums exactly 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).

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).

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 sums exactly 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$.

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 sums exactly 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).

The objective function (to minimize) is not formalized in the question. For most natural functions $f$ (e.g., when $f$ is the maximum/sum of the absolute difference between the sum of the elements in a group and the target value) this 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$.

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 sums exactly 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$.