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

Improve this question
$\endgroup$
3
  • 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$
    – David Richerby
    Jun 19, 2019 at 15:07

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.