<blockquote>
  <p>Let <span class="math-container">$c\in(0,1/2]$</span> be a constant. Given a set of positive integers with sum <span class="math-container">$S$</span>, is there a partition into two subsets such that both subsets have sum at least <span class="math-container">$cS$</span>?</p>
</blockquote>

<p>If <span class="math-container">$c=1/2$</span>, this is the famous <a href="https://en.wikipedia.org/wiki/Partition_problem" rel="nofollow noreferrer">partition problem</a> which is NP-complete. What is known about the complexity for other values of <span class="math-container">$c$</span>?</p>

CC BY-SA 4.0
2019-03-24T17:42:13.843Z
It is NP-hard for every fixed constant $c$ with $0<c<1/2$.
Gamow
CC BY-SA 4.0
2019-03-24T18:10:09.400Z
@Gamow Thanks. Could you please give a reference?
user52378
CC BY-SA 4.0
2019-06-19T15:07:08.907Z
@Gamow This is incorrect, according to [Tom van der Zanden's answer on CS SE](https://cs.stackexchange.com/a/110914/9550).
David Richerby
<partition-problem>
Partition into c and 1-c
user52378
# Partition into c and 1-c

(Asked by: username_0 on 2019-03-24)

> 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](https://en.wikipedia.org/wiki/Partition_problem) which is NP-complete. What is known about the complexity for other values of $c$?

**Tags:** partition-problem

> **Comments:**
> **username_1**: It is NP-hard for every fixed constant $c$ with $0<c<1/2$.  
> **username_0**: @username_1 Thanks. Could you please give a reference?  
> **username_2**: @username_1 This is incorrect, according to [Tom van der Zanden's answer on CS SE](https://cs.stackexchange.com/a/110914/9550).  

---

## 0 answers

