2
$\begingroup$

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known to be NP-hard, but does it have an FPTAS?

I found answers for some related problems:

Is there any FPTAS for 3-way number partitioning?

$\endgroup$
1
$\begingroup$

I found an FPTAS for a very similar problem: finding a partition such that the largest sum is as small as possible. This problem is equivalent to the problem of identical-machines scheduling: there are $m$ identical machines (in our case $m=3$), and $n$ jobs with different processing times, and we need to assign jobs to machines such that the latest completion time is as early as possible. In this paper:

Sartaj K. Sahni (1976). Algorithms for Scheduling Independent Tasks. Journal of the ACM. 23 (1): 116–127.

there is an algorithm that attains at most $1+\epsilon$ of the minimum in time $O(n\cdot (n^2 / \epsilon)^{m-1})$, which is an FPTAS for any fixed $m$.

However, this does not answer the original problem, which is to make the smallest sum as large as possible.

$\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.