Problem related to set partitioning

Question

Let $A_j=\{(a^i_j,b^i_j)~:~ 0 \leq i \leq n,\text{and } a^i_j,b^i_j \in \mathbb{Z}^+\}$

Given sets $A_1,\ldots, A_{p}$ and a positive integer $k$, the problem is to check whether there exists one element $(a^{i_j}_j,b^{i_j}_j)$ from each $A_j$ such that $\sum_{j}^{} a^{i_j}_j \geq k$ and $\sum_{j}^{} b^{i_j}_j \geq k$.

It looks like the problem is related to set partitioning problem, however, I am not sure how to get a reduction from set partitioning problem. Can someone help me to find the algorithm to solve this problem?

Answer 1

Let $OPT[t, x]$ be the maximum value of $\sum_{j=1}^t b_j^{i_j}$ that can be attained by selecting one element $(a_j^{i_j}, a_j^{i_j})$ from each of the first $t$ sets with the constraint that $\sum_{j=1}^i a_j^{i_j} \ge x$. If the constraint cannot be satisfied, let $OPT[t, x] = -\infty$.

According to the above definition we have $OPT[0, 0] = 0$ and $OPT[0, x] = -\infty$ for $x > 0$.

For $t>0$ we have: $$ OPT[t,x] = \max_{i=1, \dots, n} \left( b_t^i + OPT[t-1, \max\{x-a_t^i, 0\}] \right). $$

The answer to your problem is "yes" if and only if $OPT[p, k] \ge k$.

Since there are $O(p \cdot k)$ subproblems, each of which can be solved in $O(n)$ time, the overall time complexity of this algorithm is $O(p \cdot k \cdot n)$.

To show that your problem is NP-hard, you can notice that it is a generalization of partition problem: given a set $S = \{x_1, \dots, x_m\}$ of $m$ non-negative integers, decide whether there is a subset $S'$ of $S$ such that $\sum_{x \in S'} x = \frac{1}{2} \sum_{x \in S} x$.

To see this, define $n=2$, $p=m$, $A_j = \{ (x_j, 0), (0, x_j) \}$, and $k = \frac{1}{2} \sum_{x \in S} x$.