I have the following problem formulated as a linear integer program:
\begin{align} & \text{minimize} && \sum_{i \in n} x_i\\ & \text{subject to} && \sum_{i \in n}{a_i}x_i \ge \theta_1, \\ & && \sum_{i \in n}{b_i}x_i \ge \theta_2, \\ & && a_i \ge 0 \quad \forall i \in n , \\ & && b_i \ge 0 \quad \forall i \in n , \\ & \text{and} && x_i \in \{0,1\} \quad \forall i \in n , \end{align} for any given $\sum_i a_i \geq \theta_1 \geq 0$ and $\sum_i b_i \geq \theta_2 \geq 0$
Does anyone know anything about the complexity of this problem? If we only have the first constraint: $ \sum_{i \in n}{a_i}x_i \ge \theta_1 $, and we drop the second: $\sum_{i \in n}{b_i}x_i \ge \theta_2$ then the problem is easy, we can just sort all $a_i$ in decreasing order, and pick the top ones until the threshold $\theta_1$ is satisfied. However, it seems to me that once we add the second constraint the problem becomes much harder (possibly NP-hard). Still, the idea of sorting and greedily picking elements gives at least a 2-approximation. Any clues?