# A dominate vector subset sum problem

Let $$k$$ be some constants (e.g. one can take $$k=2$$ for simplexity), for any $$u,v\in \mathbb{R}$$, we say $$u$$ dominate $$v$$ if $$\forall 1\le i\le k,~ u[i]\ge v[i]$$, write it as $$u\succ v$$.

Consider the following problem:

Let $$v_1,v_2,\cdots,v_n\in \mathbb{R}^k$$, integer $$m\le n$$, and a target vector $$t\in\mathbb{R}^k$$, decide if there exist an index set $$I\subset [n]$$, such that $$\sum_{i\in I}v_i\succ t,$$and $$|I|\le m$$

Is this problem NP-hard? (Note that, when $$k$$ is not constant but scale as $$n$$, this problem is NP-hard by reduction from set cover problem.)

In particular, is this problem hard for $$k=2$$? (Note that, there is a pseudo-polynomial dynamic programming algorithm for integer vectors).

## 1 Answer

It's hard for $$k\ge 2$$ by a reduction from Partition. Let's first look at $$k = 3$$. Suppose that the input to Partition is the numbers $$x_1, \ldots, x_n$$, and their sum is $$S$$. For each $$i$$ create a vector $$v_i$$ whose first coordinate is $$x_i$$, second coordinate is $$-x_i$$, and the third coordinate is $$0$$. Add another vector $$v_{n+1}$$ with first coordinate $$0$$, second coordinate $$S$$, and last coordinate $$1$$. Define $$t$$ to have first and second coordinates $$S/2$$, and last coordinate $$1$$. Then any solution $$I$$ to this instance of your problem must include $$n+1$$, and the sum $$\sum_{i \in I}{v_i}$$ has first coordinate $$\sum_{i \in I\setminus \{n+1\}}{x_i}$$ and second coordinate $$\sum_{i \in [n] \setminus I}{x_i}$$, so it's only feasible if $$I \setminus \{n+1\}$$ is a valid solution to the Partition instance.

This can be extended to $$k=2$$ with a trick. Define the same instance but $$v_i$$ for $$i \in [n]$$ has only the first two coordinates. Let $$A = \sum_{i=1}^n{|x_i|}$$ and $$b = \lceil \log_2 A\rceil$$. Define $$v_{n+1}$$ to have first coordinate $$2^b$$, and second coordinate $$S$$, and $$t$$ to have first coordinate $$2^b+S/2$$ and second coordinate $$S/2$$. This forces the $$b$$-th bit (from the right) of the first coordinate of $$\sum_{i \in I}{v_i}$$ to be $$1$$, which can only happen if $$n+1 \in I$$. The rest is the same as above.

• Yes, the reduction works. Is the problem still hard if we assume $v_i$ to be positive? Thanks. – Paul Oct 29 '18 at 5:23
• If the vectors are positive then taking all of them maximizes all coordinates simultaneously. So, no, I don't think so. – Sasho Nikolov Oct 29 '18 at 14:23
• Yes, but the problem has a cardinality constraint $m$ on the subsets. But anyway, I think your reduction can be adapted to the positive case by adding some constant to the second coordinate to make them positive. – Paul Oct 29 '18 at 19:54
• I see. I never noticed this in your formulation. This is a different question, however, it's probably better to post it separately. – Sasho Nikolov Oct 29 '18 at 23:11