patternMinor
Partitioning a set so both parts have sum at least $c$ times the total sum
Viewed 0 times
totalpartitioningthehavebothleastsumpartstimesset
Problem
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$?
I posted the question to CS Theory several weeks ago. The only response was a comment that claimed that the problem is NP-hard, but the commenter never responded to my request for a proof or reference.
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$?
I posted the question to CS Theory several weeks ago. The only response was a comment that claimed that the problem is NP-hard, but the commenter never responded to my request for a proof or reference.
Solution
The problem is polynomial (even linear time) for any fixed $c (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 $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<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$.
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 $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<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$.
Context
StackExchange Computer Science Q#110908, answer score: 3
Revisions (0)
No revisions yet.