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 1


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.

  • $\begingroup$ Yes, the reduction works. Is the problem still hard if we assume $v_i$ to be positive? Thanks. $\endgroup$
    – Paul
    Commented Oct 29, 2018 at 5:23
  • $\begingroup$ If the vectors are positive then taking all of them maximizes all coordinates simultaneously. So, no, I don't think so. $\endgroup$ Commented Oct 29, 2018 at 14:23
  • $\begingroup$ 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. $\endgroup$
    – Paul
    Commented Oct 29, 2018 at 19:54
  • $\begingroup$ I see. I never noticed this in your formulation. This is a different question, however, it's probably better to post it separately. $\endgroup$ Commented Oct 29, 2018 at 23:11

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.