Partitioning a set so both parts have sum at least $c$ times the total sum
The problem is polynomial (even linear time) for any fixed $c &lt; 1/2$.

Assume no there is no item of size $&gt; (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 $&lt; 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&gt;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&lt;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$.