1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I guess, we need to add the term $b^{i_j}_j$ on right-hand side of the recurrence relation. $\endgroup$ – Kumar May 19 '20 at 1:39
  • $\begingroup$ Thank you!$\phantom{}$ $\endgroup$ – Steven May 19 '20 at 7:26

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.