4
$\begingroup$

Let $c\in(0,1/2]$ be a constant. Given a set of positive integers with sum $S$, is there a partition into two subsets such that both subsets have sum at least $cS$?

If $c=1/2$, this is the famous partition problem which is NP-complete. What is known about the complexity for other values of $c$?

I posted the question to CS Theory several weeks ago. The only response was a comment that claimed that the problem is NP-hard, but the commenter never responded to my request for a proof or reference.

$\endgroup$
3
$\begingroup$

The problem is polynomial (even linear time) for any fixed $c < 1/2$.

Assume no there is no item of size $> (1-c)S$, otherwise it is a trivial no-instance.

If there is any item $w_i$ with size $\geq cS$ we are immediately done because we can take one half of the partition to be that item.

Otherwise, all items are $< cS$. Greedily taking items means we will exceed the target sum by less than $c S$, meaning the remaining items have weight at least $(1-2c)S$. If $c\leq 1/3$, the instance trivially is a yes-instance.

For $c>1/3$, note that for the items smaller than $(1-2c)S$, we can use a greedy algorithm to assign them after we have a correct(*) solution for the large items. The number of large items is at most $1/(1-2c)$, which, for fixed $c<1/2$, is a constant. Thus, we can guess (in constant time) a solution for the large items, then use a greedy algorithm to distribute the small items. Note that the constant tends to infinity as $c$ tends to $1/2$.

(*) Where correct means neither half of the partition exceeds $cS$ by more than $(1-2c)S$.

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