1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, the reduction works. Is the problem still hard if we assume $v_i$ to be positive? Thanks. $\endgroup$ – Paul Oct 29 '18 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$ – Sasho Nikolov Oct 29 '18 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 Oct 29 '18 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$ – Sasho Nikolov Oct 29 '18 at 23:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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