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

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

CC BY-SA 4.0
2018-10-29T05:23:25.243Z
Yes, the reduction works. Is the problem still hard if we assume $v_i$ to be positive? Thanks.
Paul
CC BY-SA 4.0
2018-10-29T14:23:52.880Z
If the vectors are positive then taking all of them maximizes all coordinates simultaneously. So, no, I don't think so.
Sasho Nikolov
CC BY-SA 4.0
2018-10-29T19:54:24.193Z
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
CC BY-SA 4.0
2018-10-29T23:11:28.593Z
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
CC BY-SA 4.0
2018-10-29T04:03:01.530Z
2018-10-29T04:03:01.530Z
Sasho Nikolov
<p>Let <span class="math-container">$k$</span> be some constants (e.g. one can take <span class="math-container">$k=2$</span> for simplexity), for any <span class="math-container">$u,v\in \mathbb{R}$</span>, we say <span class="math-container">$u$</span> dominate <span class="math-container">$v$</span> if <span class="math-container">$\forall 1\le i\le k,~ u[i]\ge v[i]$</span>, write it as <span class="math-container">$u\succ v$</span>.</p>

<p>Consider the following problem:</p>

<blockquote>
  <p>Let <span class="math-container">$v_1,v_2,\cdots,v_n\in \mathbb{R}^k$</span>, integer <span class="math-container">$m\le n$</span>, and a target vector <span class="math-container">$t\in\mathbb{R}^k$</span>, decide if there exist an index set <span class="math-container">$I\subset [n]$</span>, such that
  <span class="math-container">$$\sum_{i\in I}v_i\succ t,$$</span>and <span class="math-container">$|I|\le m$</span></p>
</blockquote>

<p>Is this problem NP-hard? (Note that, when <span class="math-container">$k$</span> is not constant but scale as <span class="math-container">$n$</span>, this problem is NP-hard by reduction from set cover problem.)</p>

<p>In particular, is this problem hard for <span class="math-container">$k=2$</span>? (Note that, there is a pseudo-polynomial dynamic programming algorithm for integer vectors).</p>

<np-hardness><np-complete><dynamic-programming><subset-sum>
A dominate vector subset sum problem
Paul
# A dominate vector subset sum problem

(Asked by: username_0 on 2018-10-29)

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).

**Tags:** np-hardness, np-complete, dynamic-programming, subset-sum


---

## 1 answers

### Answer by username_1 on 2018-10-29. Score: 2

It's hard for $k\ge 2$ by a reduction from [Partition](https://en.wikipedia.org/wiki/Partition_problem). 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.

> **Comments:**
> **username_0**: Yes, the reduction works. Is the problem still hard if we assume $v_i$ to be positive? Thanks.  
> **username_1**: If the vectors are positive then taking all of them maximizes all coordinates simultaneously. So, no, I don't think so.  
> **username_0**: 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.  
> **username_1**: I see. I never noticed this in your formulation. This is a different question, however, it's probably better to post it separately.  

---

