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

  • 2
    $\begingroup$ It is NP-hard for every fixed constant $c$ with $0<c<1/2$. $\endgroup$
    – Gamow
    Mar 24, 2019 at 17:42
  • 3
    $\begingroup$ @Gamow Thanks. Could you please give a reference? $\endgroup$
    – user52378
    Mar 24, 2019 at 18:10
  • $\begingroup$ @Gamow This is incorrect, according to Tom van der Zanden's answer on CS SE. $\endgroup$ Jun 19, 2019 at 15:07


Your Answer

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

Browse other questions tagged or ask your own question.