# Problem related to set partitioning

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?

## 1 Answer

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

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