Is there an FPTAS for 3-way number partitioning?

Question

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:

• There is no FPTAS for MSSP (Multiple Subset Sum Problem) unless P=NP - https://epubs.siam.org/doi/abs/10.1137/S1052623498348481?journalCode=sjope8
• There is an FPTAS for 2-way number partitioning - https://www.sciencedirect.com/science/article/pii/S0022000003000060
• There is no FPTAS for 3-partition, since it is strongly NP-hard - https://en.wikipedia.org/wiki/3-partition_problem
• There is a PTAS for 3-way number partitioning - https://en.wikipedia.org/wiki/Multiway_number_partitioning

Is there any FPTAS for 3-way number partitioning?

Answer 1

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.