4
$\begingroup$

I've read that this SE is for research-level CS questions; this is certainly research level, just not my field of research, so it is hard for me to assess how difficult the question really is. So in case this is well-known and easy, I'd still be grateful for a hint or a reference. Thanks!

So here is the question: Given a multiset $S$ of integers (or rationals), does there exist a multi-subset $T\subsetneq S$ such that $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s|\le\sum_{s\in S}s$?

In case we replace the rhs with some constant $l\ge0$, this reduces to the subset sum decision variant, which is NP hard. But is this variant still NP-hard?

Thanks! - Josely

$\endgroup$
  • $\begingroup$ Can't you just use scaling ? Given an instance $(S, k)$, construct a new instance $S'$ where all elements have been scaled by $\sum_{s \in S} s/k$. $\endgroup$ – Suresh Venkat Mar 17 '14 at 16:14
  • $\begingroup$ @SureshVenkat: I don't think that helps, since it scales both sides of the inequality. $\endgroup$ – Josely Mar 20 '14 at 11:36
3
$\begingroup$

Note that $T=S$ and $T=\emptyset$ are trivial solutions.

With the constraints $T \neq \emptyset$ and $S\setminus T \neq \emptyset$ the problem seems (unless the proof below is wrong :-) NP-complete. A possible reduction is from PARTITION: given a set $A$ of $n$ positive integers $A=a_1,..a_n$, can $A$ be partitioned in two sets $A = A_1 \cup A_2$ such that $\sum_{a_i\in A_1} a_i = \sum_{a_j \in A_2} a_j$?

Let $M = \sum_{a_i \in A}a_i$; without loss of generality we can assume that $M$ is even.

You can pick $S = A \cup \{a_{n+1}, a_{n+2}\}$ with $a_{n+1}= a_{n+2}=-M/2$; so we have $\sum_{s \in S}s = 0$ (right hand side of the equation of your problem).

The original PARTITION problem has a solution if and only if your problem has a solution.

$(\Leftarrow)$ Suppose that there exists $T$ such that $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s|\le\sum_{s\in S}s$ = 0. So the absolute value of the difference of the sums is zero: $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s| = 0$
$T$ cannot contain both $a_{n+1}$ and $a_{n+2}$, otherwise $|\sum_{t\in T}t-\sum_{s\in S\setminus T}s| > 0$ because at least one element $a_i>0$ must be contained in $S \setminus T$ and $|-M/2 -M/2 - a_i| > M$. For the same reason $S \setminus T$ cannot contain both $a_{n+1}$ and $a_{n+2}$. So $a_{n+1} \in T$ and $a_{n+2} \in S \setminus T$, and their contribution to the absolute value of the difference of the sums is $0$. So the remaining elements must be partitioned in such a way that the sum of the elements in $T$ equals the sum of elements in $S \setminus T$ in order to have an absolute value of the difference of the sums equal to $0$.

$(\Rightarrow)$ If the original partition problem has a solution, then it is easy to see that if $T = A_1 \cup a_{n+1}$ we get an absolute value of the difference of the sums equal to $0$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you. Your proof works if we add that we can assume wlog that $S$ consists of nonnegative numbers (which we can). $\endgroup$ – Josely Mar 20 '14 at 11:35

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.