<p><strong>The problem:</strong> Let <span class="math-container">$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}$</span> be <span class="math-container">$k$</span> sets of <span class="math-container">$n$</span> integers, and let <span class="math-container">$U,L \in \mathbb{N}$</span> be integer parameters. Assume that for all <span class="math-container">$i \in [k]$</span> it holds that <span class="math-container">$a^i_1 \leq a^i_2 \leq \ldots \leq a^i_n$</span>. The goal is to find <span class="math-container">$r_1,\ldots,r_k \in [n]$</span> (possibly with repetition) such that</p>
<p><span class="math-container">$$\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.$$</span></p>
<p>In words, we take <span class="math-container">$k$</span> 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 <span class="math-container">$U$</span>; at the same time, we want that the total sum of the corresponding suffixes (e.g., the corresponding suffix of <span class="math-container">$a^i_1,a^i_2$</span> is <span class="math-container">$a^i_n,a^i_{n-1}$</span>) to be lower bounded by <span class="math-container">$L$</span>.</p>
<p><strong>Question: Is this problem NP-Hard?</strong></p>

CC BY-SA 4.0
2023-06-10T16:16:41.487Z
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$?
SamM
CC BY-SA 4.0
2023-06-18T10:31:46.043Z
Seems like a nice homework question.
Neal Young
<np-hardness><partition-problem><packing>
Is this Knapsack/Subset Sum Variant NP-Hard?
John
# Is this Knapsack/Subset Sum Variant NP-Hard?

(Asked by: username_0 on 2023-06-10)

**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?**

**Tags:** np-hardness, partition-problem, packing
> **Comments:**
> **username_1**: 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$?  
> **username_2**: Seems like a nice homework question.  

---

## 0 answers

