The problem: Let $A_1 = \{a^1_1,\ldots,a^1_n\}, A_2 = \{a^2_1,\ldots,a^2_n\}, \ldots, A_k = \{a^k_1,\ldots,a^k_n\} \subset \mathbb{N}$ be $k$ sets of $n$ integers, and let $U,L \in \mathbb{N}$ be integer parameters. Assume that for all $i \in [k]$ it holds that $a^i_1 \leq a^i_2 \leq \ldots \leq a^i_n$. The goal is to find $r_1,\ldots,r_k \in [n]$ (possibly with repetition) such that

$$\sum_{i \in [k]} \sum_{j \in [r_i]} a^i_j \leq U, ~~~\sum_{i \in [k]} \sum_{j \in [r_i]} a^i_{n-j+1} \geq L.$$

In words, we take $k$ prefixes, one for each set, according to a sorted way, and we want that the total sum of the prefixes to be upper bounded by $U$; at the same time, we want that the total sum of the corresponding suffixes (e.g., the corresponding suffix of $a^i_1,a^i_2$ is $a^i_n,a^i_{n-1}$) to be lower bounded by $L$.

Question: Is this problem NP-Hard?

  • 1
    $\begingroup$ Can we reduce from partition with a set $S$ by setting $n=1$, $A_i = \{s_i\}$ for all $i$, and $U = L = \sum_{s\in S} s/2$? $\endgroup$
    – SamM
    Jun 10, 2023 at 16:16
  • $\begingroup$ Seems like a nice homework question. $\endgroup$
    – Neal Young
    Jun 18, 2023 at 10:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.