# Partitioning a set so both parts have sum at least $c$ times the total sum

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.

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