4
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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/…. $\endgroup$ Jun 13, 2022 at 13:54

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.