3
$\begingroup$

Given a set of integers $S=\{a_1, \dots, a_n\}$ where $a_i > 0$ and $n$ is an even number, we want to find $A \subset S$ so that:

$ \left| \sum_{a \in A}a - \sum_{b \in S-A}b \right| $

is minimized. This problem is very well known to be NP-hard. If we add a constraint $|A| = |S-A|$, is the problem is still NP-hard?

2 Answers 2

8

Yes, because you can multiply all of the existing numbers in $S$ by $2|S|^2$ and extend $S$ with the numbers $1$ through $|S|$. A minimal solution to the extended problem with the $2|A|=|S|$ constraint will then also be a solution to the original problem without such constraint, just by ignoring what happened to the new integers in it.

If someone gives me a polynomial solver for the constrained problem, I can use this reduction to solve the original problem in polynomial time. Thus, since the original problem is known to be NP-hard, the constrained one is NP-hard too.

For example, $\{100,200,300\}$ without constraint reduces to $\{1,2,3,1800,3600,5400\}$ with constraint. The optimal solution to the latter problem is $\{3,1800,3600\},\{1,2,5400\}$, with a difference of $|5403-5403|=0$. Because this difference is strictly less than $3^2$, the original unconstrained $\{100,200,300\}$ has a solution with difference strictly less than 1.

  • 0
    @HenningMakholm: I got it. You're wonderful man :) Actually, your description in the answer was a bit vague, but it's clear now.2011-11-24
3

Garey and Johnson, Computers and Intractability, page 223:

"A3.2 Weighted set problems

"[SP12] Partition

"Instance: Finite set $A$ and a size $s(a)$ in ${\bf Z}^+$ for each $a$ in $A$.

"Question: Is there a subset A'\subseteq A such that \sum_{a\in A'}s(a)=\sum_{a\in A-A'}s(a)?

"Reference: [Karp, 1972]. Transformation from 3-dimensional matching (see Section 3.1.5).

"Comment: Remains NP-complete even if we require that |A'|=|A|/2 ...."

I'm aware that this is about equality while the original is about minimization. Still, might not be a bad idea to see what's in the book.

  • 3
    The statement you quoted alone already implies that the problem in the question is NP-hard. (Exercise: why?)2011-11-25