Consider the following decision problem:
We have a set of vectors $S \subseteq \mathbb Z^2$, and a target $k$. Is there a subset $S' \subseteq S$ such that $\sum_{v \in S'} v$ has both coordinates greater than or equal to $k$?
This question came up naturally in the course of doing some (hobby) research on another problem, and it would help if it were easy to quickly solve instances of this problem.
Does this decision problem have a name? Is it tractable, is it NP-complete, or something else?
It looks a lot like the classical knapsack decision problem. That one is NP-complete, but it becomes tractable if the weights are required to be "small" (i.e., they are at most polynomial in the size of the input). Does it help if $k$ and the coordinates are relatively small in the same way?
The problem is weakly $\mathcal{NP}$-complete.
Here is a reduction from the knapsack problem, with capacity $B$, $n$ objects of weight $w_i$ and value $c_i$, and of objective value $K$ (We want to decide if we can take more than $K$ as an objective value).
We take the coordinates $(K+B, 0), (-w_i, c_i)_{i=1...n}$.
We need to take the first coordinate. We then need to find a set $S$ of coordinates $(-w_i, c_i)_{i\in S}$ such that $\sum_{i\in S}c_i \geq K$ and $K+B + \sum_{i\in S} -w_i\geq K$, so $ \sum_{i\in S} w_i\leq B$.
Reciprocally, we can reduce to the knapsack problem. Given $(x_i, y_i)_{i=1...n}$ a set of coordinates and $K$ the target, we build a knapsack instance $B = \sum_{x_i\geq 0} x_i - K$ and objects of weight $|x_i|$, of value $-\text{sign}(x_i)y_i$ and a target $K-\sum_{x_i\geq 0} y_i$ (with $\text{sign}(0) = 1$).