As input, given two finite sets of integers $X = \{x_1,...,x_m\}$, $Y = \{y_1,...,y_n\} \subseteq Z$, and a non-negative integer $v ≥ 0$. The goal is to decide if there are non-empty subsets $S ⊆ [m]$ and $T ⊆ [n]$ such that

$$ \left|\sum_{i\in S}x_i-\sum_{j\in T} y_j\right| \leq v$$

How to show this problem is NP-hard? I'm quite confused. What I got so far is to reduce from subset sum problems, since the form is set to less than v. So I need to have 2v+1 subset sum problems to verify


1 Answer 1


The special case where $v=0$ and $Y=\{\frac12\sum_{i=1}^m x_i\}$ is the partition problem, which is NP-complete.


Your Answer

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

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