minimum number of 2d elements whose sums across both dimensions satisfy some threshold

Question

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$

Another way of looking at it, is that we have a number of 2d tuples and we want to select the minimum number of tuples such that the sums over both dimensions are greater or equal to two thresholds. 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$ (1D variant) 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?

Answer 1

Your problem is NP-hard, by reduction from the equal-cardinality partition problem.

Let $a_1,\dots,a_n$ be an instance of the equal-cardinality partition problem (so $n$ is even). The reduction works as follows. Choose a sufficiently large constant $C$. Define $b_i = C-a_i$, $\theta_1 = (a_1+\dots+a_n)/2$, $\theta_2 = nC/2 - \theta_1$.

Now if there is a solution to the equal-cardinality partition problem, then there is a solution to your problem with $x_1+\dots+x_n \le n/2$. Proof: In particular, we can set $x_i=1$ for each element in the first part; since both parts have equal cardinality, this sets $n/2$ of the $x_i$'s to 1; and then since it is a solution to the partition problem, we have $\sum_i a_ix_i = \theta_1$ and

$$\sum_i b_ix_i = \sum_i Cx_i - \sum_i a_ix_i = nC/2 - \theta_1 = \theta_2,$$

hence this is a valid solution to your problem.

Also, if there is a solution to your problem with $x_1+\dots+x_n \le n/2$, then it yields a solution to the equal-cardinality partition problem. Proof: If $C$ is chosen to be sufficiently large, then the only way to satisfy $\sum_i b_i x_i \ge \theta_2$ is to have $x_1+\dots+x_n \ge n/2$, so we must have $x_1 + \dots + x_n = n/2$. Therefore we can put all $a_i$'s where $x_i=1$ into the first part, and all others into the second part, and the two parts will have equal cardinality. Now since $x_1+\dots+x_n = n/2$, we have

$$\sum_i a_i x_i = nC/2 - \sum_i b_i x_i \le nC/2 - \theta_2 = \theta_1,$$

which together with the constraint $\sum_i a_i x_i \ge \theta_1$ implies that $\sum_i a_i x_i = \theta_1 = (a_1+\dots+a_n)/2$, so these two parts form a solution to the partition problem.

This means that this yields a valid reduction, and thus a proof of NP-hardness.