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?

  • $\begingroup$ Hint: Take $b_i = -a_i$ and $\theta_2 = -\theta_1$. $\endgroup$ Dec 1, 2022 at 6:56
  • 2
    $\begingroup$ @YuvalFilmus: $a,b\ge0$. $\endgroup$ Dec 1, 2022 at 8:44
  • 1
    $\begingroup$ IMO, describing the problem as a (0-1) linear program does obscure the question. $\endgroup$ Dec 1, 2022 at 8:45
  • $\begingroup$ WLOG, $\theta_1=\theta_2=1$. $\endgroup$ Dec 1, 2022 at 9:10

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

  • $\begingroup$ Thanks for the quick answer. Inspired by it, I also figured out a reduction from k-subset-sum. I also have to deal with the case when the inequalities are strict (greater than instead of greater or equal to). But the proof then seems much harder to me. We can no longer force the two inequalities to become equalities, like in partitioning or subset sum-type problems... $\endgroup$ Dec 1, 2022 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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