Can almost equal partition problem be solved in polynomial time?

Given a list of positive integers with sum $$s$$, decide if there is a subset with sum $$0.5s$$. This is the well-known PARTITION problem, which is NP-hard.

What about the following: Given a list of positive integers with sum $$s$$, decide if there is a subset with sum in the range $$[0.49s, 0.51s]$$. Can this problem be solved in polynomial time?

• There is a PTAS for a variant of the problem that minimizes the spread between the parts. I suspect that it could be used to solve the problem in polynomial time (might be wrong though). See en.wikipedia.org/wiki/…. Jun 13, 2022 at 13:54

1 Answer

Yes, this problem is polynomial-time solvable.

Let $$A$$ be the input numbers and let $$S = \mathrm{sum}(A)$$ be its sum. Let $$T_1 = 0.49S$$, $$T_2 = 0.51 S$$ be the target sum range. Let $$\epsilon = 0.02$$ so that $$T_2 - T_1 = \epsilon S$$.

Define $$A_1 = \{ a \in A \mid a \geq \epsilon S \}$$ to be large items and $$A_2 = A \setminus A_1$$ to be small items.

Proposition: For a subset of large items $$X \subseteq A_1$$, there exist a solution containing that subset if and only if $$T_1 - \mathrm{sum}(A_2) \leq \mathrm{sum}(X) \leq T_2$$.

The "only if" direction is from the fact that the range of possible sum containing the subset $$X$$ is $$[\mathrm{sum}(X), \mathrm{sum}(X) + \mathrm{sum}(A_2)]$$ (note the assumption of all items are nonnegative) and it must have a non-empty intersection with $$[T_1, T_2]$$.

To prove the "if" direction, consider adding small items arbitrary as long as the sum is less than the lower bound $$T_1$$. Because added items are small, it cannot overshoot the upper bound $$T_2$$.

Now, we have an algorithm solving the problem by brute-forcing all subsets $$X \subseteq A_1$$ of large items and checking its sum. The time complexity of the algorithm is $$O(n + 2^{|A_1|} |A_1|)$$. Because we have $$|A_1| \leq \epsilon^{-1}$$, the time complexity is polynomial in $$n$$ for a constant $$\epsilon$$. The exponent can be reduced to half using the meet-in-the-middle approach.