patternMinor
Is there an FPTAS for 3-way number partitioning?
Viewed 0 times
numberfptaswayfortherepartitioning
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#141078, answer score: 2
Revisions (0)
No revisions yet.