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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.