<p><strong>Your problem <span class="math-container">$P$</span>:</strong> given a multiset <span class="math-container">$S = \{a_1, \dots, a_m\}$</span> of some <span class="math-container">$m_1$</span> elements equal to <span class="math-container">$a \in \mathbb{Z}^+$</span> and <span class="math-container">$m_2$</span> elements equal to <span class="math-container">$b \in \mathbb{Z}^+$</span>, and <span class="math-container">$k \in \mathbb{N}$</span>, what is the <span class="math-container">$k$</span>-partition <span class="math-container">$S_1, \dots, S_k$</span> which maximizes <span class="math-container">$\min_i \sum_{a_j \in S_i} a_j$</span>.</p>
<p><strong>Definition</strong> A &quot;disjoint collection&quot; of subsets of <span class="math-container">$S$</span> is a collection of subsets of <span class="math-container">$S$</span> that are disjoint. A &quot;disjoint <span class="math-container">$k$</span>-collection&quot; is a disjoint collection with <span class="math-container">$k$</span> subsets.</p>
<p><strong>Consider problem <span class="math-container">$P'$</span>:</strong> given a multiset <span class="math-container">$S$</span> of <span class="math-container">$m_1$</span> elements equal to <span class="math-container">$a \in \mathbb{Z}^+$</span> and <span class="math-container">$m_2$</span> elements equal to <span class="math-container">$b \in \mathbb{Z}^+$</span>, and <span class="math-container">$T \in \mathbb{Z}^+$</span>, what is the maximally sized disjoint collection of subsets of <span class="math-container">$S$</span> which has the property that each subset's sum is <span class="math-container">$\ge T$</span>?</p>
<p><strong>Claim 1</strong> if we can solve <span class="math-container">$P'$</span> in poly-time we can solve <span class="math-container">$P$</span> in poly-time.</p>
<p><em>Proof of Claim 1</em>: We reduce <span class="math-container">$P$</span> to <span class="math-container">$P'$</span> using binary search. Let <span class="math-container">$A'$</span> denote the assumed poly-time algorithm for <span class="math-container">$P'$</span>.</p>
<p>So we have <span class="math-container">$S$</span> and some <span class="math-container">$k$</span> as input from <span class="math-container">$P$</span>. Let <span class="math-container">$T^*$</span> denote the optimal minimum-set-sum (the value we're trying to find to answer <span class="math-container">$P$</span>).</p>
<p>We will call <span class="math-container">$A'$</span> with the same <span class="math-container">$S$</span> and various <span class="math-container">$T$</span>s as input.</p>
<p>Let <span class="math-container">$\tilde{T}$</span> be the maximal <span class="math-container">$T \in \mathbb{Z}^+$</span> for which <span class="math-container">$A'$</span> returns a collection of size at least <span class="math-container">$k$</span>.</p>
<p>We claim that <span class="math-container">$\tilde{T} = T^*$</span>.</p>
<p>First, let's show <span class="math-container">$\tilde{T} \le T^*$</span>: to see this, by definition of <span class="math-container">$\tilde{T}$</span>, note that <span class="math-container">$A'$</span> produces a set of at least <span class="math-container">$k$</span> subsets each of whom has sum <span class="math-container">$\ge \tilde{T}$</span>; add the &quot;leftover&quot; elements outside to any subset in the collection; now we have a <span class="math-container">$k$</span>-partition with each subset having sum <span class="math-container">$\ge \tilde{T}$</span>. But <span class="math-container">$T^*$</span> is the maximal <span class="math-container">$T$</span> with this property: so <span class="math-container">$T^* \ge \tilde{T}$</span>.</p>
<p>Next, let's show <span class="math-container">$\tilde{T} \ge T^*$</span>: by definition of <span class="math-container">$T^*$</span>, there is some <span class="math-container">$k$</span>-partition of <span class="math-container">$S$</span> all of whose subsets sum to <span class="math-container">$\ge T^*$</span>. So if we feed <span class="math-container">$S$</span>, <span class="math-container">$T^*$</span> as input to <span class="math-container">$A'$</span>, <span class="math-container">$A'$</span> will return a collection of size at least <span class="math-container">$k$</span>. But <span class="math-container">$\tilde{T}$</span> is the maximal such <span class="math-container">$T$</span>, so <span class="math-container">$\tilde{T} \ge T^*$</span>.</p>
<p>We know that <span class="math-container">$\tilde{T} = T^*$</span> lies between <span class="math-container">$T=1$</span> and <span class="math-container">$T=\lfloor (\sum_{a_i \in S} a_i) / k \rfloor \le m_1a + m_2b$</span>.</p>
<p>So to find <span class="math-container">$\tilde{T}$</span>, we need only <span class="math-container">$O(\log(m_1a + m_2b))$</span> calls to <span class="math-container">$A'$</span> with binary search: any <span class="math-container">$T$</span> for which we get a collection of size <span class="math-container">$\ge k$</span> from <span class="math-container">$A'$</span> is <span class="math-container">$\le \tilde{T}$</span>; any <span class="math-container">$T$</span> for which we get a collection of size <span class="math-container">$&lt; k$</span> from <span class="math-container">$A'$</span> is <span class="math-container">$&gt; \tilde{T}$</span>. <span class="math-container">$\square$</span></p>
<p>Now we show (or *claim to show*) that <span class="math-container">$P'$</span> can be solved in poly-time:</p>
<hr />
<p><strong>Problem <span class="math-container">$P'$</span></strong>: given a multiset <span class="math-container">$S$</span> of <span class="math-container">$m_1$</span> elements equal to <span class="math-container">$a \in \mathbb{Z}^+$</span> and <span class="math-container">$m_2$</span> elements equal to <span class="math-container">$b \in \mathbb{Z}^+$</span>, and <span class="math-container">$T \in \mathbb{Z}^+$</span>, what is the maximally sized disjoint collection of subsets of <span class="math-container">$S$</span> which has the property that each subset's sum is <span class="math-container">$\ge T$</span>?</p>
<p><strong>Claim 2</strong> we can solve <span class="math-container">$P'$</span> in poly-time.</p>
<p>Let <span class="math-container">$\ell^*$</span> denote the size maximal size disjoint collection (we are looking for <span class="math-container">$\ell^*$</span> and a disjoint collection that achieves this maximum).</p>
<p><em>First some definitions</em>:</p>
<p><strong>Definition</strong> call multisets consisting of only <span class="math-container">$a$</span>'s and <span class="math-container">$b$</span>'s, &quot;<span class="math-container">$(a, b)$</span>-multisets&quot;. Any such multiset can be identified by an ordered pair <span class="math-container">$(i, j)$</span> where <span class="math-container">$i$</span> denotes the number of <span class="math-container">$a$</span>'s and <span class="math-container">$j$</span> denotes the number of <span class="math-container">$b$</span>'s.</p>
<p><strong>Definition</strong> &quot;<span class="math-container">$(a,b,T)$</span>-minimal multisets&quot; <span class="math-container">$(i, j)$</span> are those <span class="math-container">$(a,b)$</span>-multisets for which removing any element would bring you to a sum below <span class="math-container">$T$</span>: i.e. <span class="math-container">$ai + bj \ge T$</span>, but <span class="math-container">$a(i-1) + bj &lt; T$</span> and <span class="math-container">$ai + b(j-1) &lt; T$</span>. For example, if <span class="math-container">$a=2$</span> and <span class="math-container">$b=5$</span> and <span class="math-container">$T=20$</span>, the minimal multisets would be <span class="math-container">$(10, 0)$</span>, <span class="math-container">$(8, 1)$</span>, <span class="math-container">$(5, 2)$</span>, <span class="math-container">$(3, 3)$</span> and <span class="math-container">$(0, 4)$</span>.</p>
<p><em>Observation</em>: Without loss of generality,  we can assume that the optimal collection of <span class="math-container">$\ell^*$</span> subsets of <span class="math-container">$S$</span> consists of only <span class="math-container">$(a, b,T)$</span>-minimal multisets. To see why this is without loss of generality, consider any collection of <span class="math-container">$\ell^*$</span> subsets of <span class="math-container">$S$</span>, each with sum <span class="math-container">$\ge T$</span>: remove as many elements as you can from each of these subsets, while maintaining the invariant that each must have sum <span class="math-container">$\ge T$</span>. Once you cannot remove any more, you have a collection of <span class="math-container">$\ell^*$</span> <span class="math-container">$(a,b,T)$</span>-minimal subsets. So indeed it is fine to look only for collections of <span class="math-container">$(a,b,T)$</span>-minimal multisets.</p>
<p>Note that there are not so many &quot;minimal&quot; <span class="math-container">$(a,b,T)$</span>-multisets that can be subsets of <span class="math-container">$S$</span>: we can crudely bound by <span class="math-container">$\min(m_1, m_2)+1$</span> (since no two minimal multisets can have either coordinate equal).</p>
<p>Call the actual number of these minimal multisets that are also subsets of <span class="math-container">$S$</span> as <span class="math-container">$M$</span>. Order these <span class="math-container">$M$</span> subsets in say lexicographically decreasing order (like we did above), and call them <span class="math-container">$(i_1, j_1), (i_2, j_2), \dots, (i_p, j_p),\dots, (i_M, j_M)$</span>.</p>
<p>We claim to solve <span class="math-container">$P'$</span> in poly-time with a dynamic programming approach (where we'll construct the optimal <span class="math-container">$\ell^*$</span> minimal multisets in lexicographically decreasing order):</p>
<p>Our overall problem is to compute the maximum number of disjoint <span class="math-container">$(i_p, j_p)$</span>s we can find among the base set <span class="math-container">$S = (m_1, m_2)$</span>.</p>
<p>Let <span class="math-container">$F(M', m_1', m_2')$</span> be defined as the maximally sized disjoint collection of <span class="math-container">$(m_1', m_2')$</span> you can find, where all the subsets must be one of the lexicographically smallest <span class="math-container">$M'$</span> subsets of the <span class="math-container">$M$</span> <span class="math-container">$(a,b,T)$</span>-minimal subsets we identified, i.e. <span class="math-container">$(i_{M-M'+1}, j_{M-M'+1}), (i_{M-M'+2}, j_{M-M'+2}) ..., (i_M, j_M)$</span>.</p>
<p>We want to find <span class="math-container">$F(M, m_1, m_2)$</span>.</p>
<p>We have the recurrence <span class="math-container">$$F(M, m_1, m_2) = 1 + \max_{p=1, 2, \dots, M} F(M-p+1, m_1-i_p, m_2-j_p)$$</span> and similarly <span class="math-container">$$F(M', m_1', m_2') = 1 + \max_{p=M-M'+1, \dots, M} F(M-p+1, m'_1-i_p, m'_2-j_p).$$</span> In each subproblem none of the 3 coordinates ever increase, and always either <span class="math-container">$m_1'$</span> or <span class="math-container">$m_2'$</span> decreases.</p>
<p>The running time of this dynamic programming is bounded by <span class="math-container">$O(M (Mm_1m_2)) = O((m_1+m_2)^4)$</span>, as we wanted (strictly, the DP only gives the value of <span class="math-container">$\ell^*$</span> and not an achieving disjoint <span class="math-container">$\ell^*$</span>-collection, but I think an actual optimal solution should be able to be constructed from the DP table as well). <span class="math-container">$\square$</span>.</p>

CC BY-SA 4.0
2021-03-28T16:43:57.663Z
Thank you for the answer. I have one question regarding the Observation. When $T$ is small, it is possible that the value of the minimum-valued subset in the optimal partition of $S$ is well beyond $T$. In this case, we cannot say that all the subsets are minimal as you defined.
ashtavakra
CC BY-SA 4.0
2021-03-28T19:53:59.393Z
I admittedly had not thought specifically about this case, but the observation should still hold. "Minimal" subsets for $T$ are defined in reference to a particular $a$, $b$.  

Like if $a$ and $b$ are both larger than $T$, then by definition the "minimal" $(a, b)$-subsets are the singleton sets $\{a\}$ and $\{b\}$, and the optimally large collection of $\ell$ subsets of $S$ is the partition of $S$ into singletons.  

If $a < T < b$, then there are 2 minimal subsets: $\{b\}$ and the set consisting of $\lceil T / a \rceil$ copies of $a$.
xmq
CC BY-SA 4.0
2021-03-30T00:10:44.950Z
My point was that for certain values of $T$, the total number of items in the union of $\ell$ minimal subsets w.r.t. $T$ need not equal $m$, the total number of items. Perhaps you could clarify what you mean by "maximally sized collection of ℓ of disjoint subsets of S" in your definition of $P'$. Thank you!
ashtavakra
CC BY-SA 4.0
2021-03-30T02:02:58.053Z
Oh hm. So $P'$ is a problem where given some $T$, you want to find as many disjoint subsets of $S$ as possible that have sum $\ge T$. It's sort of a "dual" problem to $P$, informally speaking.

A "collection of $\ell$ [of] disjoint subsets of $S$" (second "of" should be deleted) is similar to an $\ell$-partition of $S$, except that the union of the $\ell$ subsets need not be equal to the full $S$ [there can be some "leftover" elements of $S$].

So I see now you are right that the observation as stated is wrong (but a close relative, which is what I sort of meant, is right - contd)...
xmq
CC BY-SA 4.0
2021-03-30T02:07:08.897Z
Let $\ell^*$ denote the optimal value. My claim is that given any optimal collection -- i.e. any collection of $\ell^*$ subsets of $S$ each of whose sum is $\ge T$, you can easily transform this into a collection of $\ell^*$ "minimal" subsets of $S$ as follows: for any subset, just remove elements and put them into the "leftover" pile until you can no longer remove elements. You're now left with $\ell^*$ "minimal" subsets. This establishes that we're ok to only search of collections of "minimal" subsets, rather than any possible collection of subsets, so the rest proceeds the same.
xmq
CC BY-SA 4.0
2021-03-30T02:10:07.547Z
But this sentence -- "Any optimal collection of ℓ subsets of our multiset  [aka (1,2)], can be assumed to consist of "minimal" (,)-multisets" -- is not true; will plan to edit this (I do still think the proof overall still works though).

I'm not sure if this addresses your exact concerns -- I don't know if I'm fully understanding the latest one -- but yeah.
xmq
CC BY-SA 4.0
2021-03-30T02:19:37.380Z
Additionally: if relevant, some detail on reduction from from $P$ to $P'$: suppose for some $T$, $P'$ returns a collection of size at least $k$ -- then certainly you can find a $k$-partition of $S$ with each subset summing to $\ge T$ (you can throw the "leftover" elements into any other set, and now it's a partition).

If for some $T$, $P'$ returns a collection of size $< k$ -- this means there is no collection of $k$ disjoint subsets of $S$, and in particular no $k$-partition, with each subset having sum $\ge T$.

So reduction from $P$ to $P'$ should work.
xmq
CC BY-SA 4.0
2021-03-30T03:24:00.400Z
Edited a bunch, going off of these comments.
xmq
CC BY-SA 4.0
2021-03-27T07:10:15.437Z
2021-03-30T03:29:13.187Z
2021-03-30T03:29:13.187Z
xmq
<p>The standard pseudo-polynomial time algorithm for the partition problem with a slight change solves this problem in polynomial time.</p>
<p>The difference with the standard subset-sum or partition problem is the following: for the subset sum problem, to achieve a value <span class="math-container">$T$</span>, you have to examine <span class="math-container">$T$</span> values of the corresponding table, however, in this case, all we have to do is to examine <span class="math-container">$O(n^2)$</span> values. Since if <span class="math-container">$T=i\cdot a + j\cdot b$</span> (assuming <span class="math-container">$T$</span> is a round number and it can be written in this form, otherwise, it is possible to change the algorithm), there are at most <span class="math-container">$n$</span> occurrences of <span class="math-container">$a$</span> and at most <span class="math-container">$n$</span> occurrences of <span class="math-container">$b$</span> (assuming the multiset has <span class="math-container">$n$</span> members), you have to check at most <span class="math-container">$n^2$</span> values to obtain <span class="math-container">$T$</span> (instead of <span class="math-container">$T$</span> values). Generally speaking, if there are <span class="math-container">$d$</span> different values, we have to check at most <span class="math-container">$n^d$</span> values for <span class="math-container">$T$</span> (this is just a very naive approach though, there might be faster approaches, like <span class="math-container">$f(d) Poly(n)$</span> checks). Note that the standard pseudo-polynomial-time algorithm for the <span class="math-container">$2$</span>-partition problem extends to the one that has to partition the input into <span class="math-container">$k$</span> sets of (almost) equal sizes, and as long as <span class="math-container">$k$</span> is a constant, <a href="https://en.wikipedia.org/wiki/Multiway_number_partitioning#Exact_algorithms" rel="nofollow noreferrer">it gives a pseudopolynomial time algorithm</a>; in the case that number of possible values is limited, this is a polynomial-time algorithm.</p>
<p>However, there is a catch here. In your question, the input is given as a real multiset with all its elements and you asked to be polynomial w.r.t. that input size, however, the multiset can be represented by only <span class="math-container">$4$</span> numbers <span class="math-container">$a,b,i,j$</span>: <span class="math-container">$i$</span> determines how many <span class="math-container">$a$</span>'s are in the multiset and <span class="math-container">$j$</span> determines how many <span class="math-container">$b$</span>'s are in the multiset. In this case, the above approach has to still examine <span class="math-container">$O(i\cdot j)$</span> values, but the input size is <span class="math-container">$O(\log (a+b+i+j))$</span>, which means that if e.g. <span class="math-container">$i&gt;&gt;\log (a+b)$</span> the above algorithm is not necessarily polynomial-time anymore. I don't know if it is possible to solve this problem in <span class="math-container">$Poly (\log (a+b+i+j))$</span>.</p>

CC BY-SA 4.0
2021-03-30T09:41:04.530Z
2021-03-30T09:41:04.530Z
Saeed
<p>I'm interested in the complexity of the following problem: Given a multiset <span class="math-container">$S$</span> containing only two positive integers <span class="math-container">$a$</span> and <span class="math-container">$b$</span>, find a <span class="math-container">$k$</span>-partition of <span class="math-container">$S$</span> that maximizes the sum of part with smallest sum. This a restricted case of the <span class="math-container">$k$</span>-way number partitioning problem, which is NP-hard. When <span class="math-container">$k=2$</span>, one can view this as a variant of the Subset-Sum problem, which is also NP-hard in general.</p>
<p>I'm wondering if the additional restriction of there being only two values in the multiset can be leveraged to design an efficient algorithm, or the problem remains NP-hard even with this restriction. For instance, minimizing the makespan (distribute jobs to machines in order to minimize the largest completion time) is polynomial-time solvable when all jobs are of length 1 or 2.</p>
<p>I am interested in the case where <span class="math-container">$k$</span> is not constant. When <span class="math-container">$k$</span> is fixed, the problem can be solved using linear programming. Concretely, the problem is:</p>
<p>Given a multiset <span class="math-container">$S = \{a_1,\dots,a_m\}$</span>, where <span class="math-container">$a_i\in\{a,b\}$</span> for <span class="math-container">$a,b\in\mathbb{Z}^{+}$</span>, and <span class="math-container">$k\in\mathbb{N}$</span>, compute a <span class="math-container">$k$</span>-partition <span class="math-container">$S_1,\dots,S_k$</span> of <span class="math-container">$S$</span> which maximizes <span class="math-container">$\min_i \sum_{a_j\in S_i} a_j$</span>. I am looking either for an algorithm that runs in time polynomial in <span class="math-container">$m,k,\log a,\log b$</span>, or a proof of NP-hardness.</p>
<p>Any leads would be appreciated!</p>

CC BY-SA 4.0
2021-03-25T02:39:40.390Z
You are suggesting that we (almost)-equally divide the $a$'s and the $b$'s in all the parts. I think this will work when $b|a$, but not in general. Consider $S=\{3,3,2,2,2\}$. The optimal partition is $\{3,3\},\{2,2,2\}$, whereas your approach will give $\{3,2\},\{3,2,2\}$.
ashtavakra
<np-hardness><approximation-algorithms><partition-problem><subset-sum>
Two valued variant of subset sum problem
ashtavakra
# Two valued variant of subset sum problem

(Asked by: username_0 on 2021-03-25)

I'm interested in the complexity of the following problem: Given a multiset $S$ containing only two positive integers $a$ and $b$, find a $k$-partition of $S$ that maximizes the sum of part with smallest sum. This a restricted case of the $k$-way number partitioning problem, which is NP-hard. When $k=2$, one can view this as a variant of the Subset-Sum problem, which is also NP-hard in general.

I'm wondering if the additional restriction of there being only two values in the multiset can be leveraged to design an efficient algorithm, or the problem remains NP-hard even with this restriction. For instance, minimizing the makespan (distribute jobs to machines in order to minimize the largest completion time) is polynomial-time solvable when all jobs are of length 1 or 2.

I am interested in the case where $k$ is not constant. When $k$ is fixed, the problem can be solved using linear programming. Concretely, the problem is:

Given a multiset $S = \{a\_1,\dots,a\_m\}$, where $a\_i\in\{a,b\}$ for $a,b\in\mathbb{Z}^{+}$, and $k\in\mathbb{N}$, compute a $k$-partition $S\_1,\dots,S\_k$ of $S$ which maximizes $\min\_i \sum\_{a\_j\in S\_i} a\_j$. I am looking either for an algorithm that runs in time polynomial in $m,k,\log a,\log b$, or a proof of NP-hardness.

Any leads would be appreciated!

**Tags:** np-hardness, approximation-algorithms, partition-problem, subset-sum

> **Comments:**
> **username_0**: You are suggesting that we (almost)-equally divide the $a$'s and the $b$'s in all the parts. I think this will work when $b|a$, but not in general. Consider $S=\{3,3,2,2,2\}$. The optimal partition is $\{3,3\},\{2,2,2\}$, whereas your approach will give $\{3,2\},\{3,2,2\}$.  

---

## 2 answers

### Answer by username_1 on 2021-03-27. Score: 0 | Accepted answer

**Your problem $P$:** given a multiset $S = \{a\_1, \dots, a\_m\}$ of some $m\_1$ elements equal to $a \in \mathbb{Z}^+$ and $m\_2$ elements equal to $b \in \mathbb{Z}^+$, and $k \in \mathbb{N}$, what is the $k$-partition $S\_1, \dots, S\_k$ which maximizes $\min\_i \sum\_{a\_j \in S\_i} a\_j$.

**Definition** A "disjoint collection" of subsets of $S$ is a collection of subsets of $S$ that are disjoint. A "disjoint $k$-collection" is a disjoint collection with $k$ subsets.

**Consider problem $P'$:** given a multiset $S$ of $m\_1$ elements equal to $a \in \mathbb{Z}^+$ and $m\_2$ elements equal to $b \in \mathbb{Z}^+$, and $T \in \mathbb{Z}^+$, what is the maximally sized disjoint collection of subsets of $S$ which has the property that each subset's sum is $\ge T$?

**Claim 1** if we can solve $P'$ in poly-time we can solve $P$ in poly-time.

*Proof of Claim 1*: We reduce $P$ to $P'$ using binary search. Let $A'$ denote the assumed poly-time algorithm for $P'$.

So we have $S$ and some $k$ as input from $P$. Let $T^\*$ denote the optimal minimum-set-sum (the value we're trying to find to answer $P$).

We will call $A'$ with the same $S$ and various $T$s as input.

Let $\tilde{T}$ be the maximal $T \in \mathbb{Z}^+$ for which $A'$ returns a collection of size at least $k$.

We claim that $\tilde{T} = T^\*$.

First, let's show $\tilde{T} \le T^\*$: to see this, by definition of $\tilde{T}$, note that $A'$ produces a set of at least $k$ subsets each of whom has sum $\ge \tilde{T}$; add the "leftover" elements outside to any subset in the collection; now we have a $k$-partition with each subset having sum $\ge \tilde{T}$. But $T^\*$ is the maximal $T$ with this property: so $T^\* \ge \tilde{T}$.

Next, let's show $\tilde{T} \ge T^\*$: by definition of $T^\*$, there is some $k$-partition of $S$ all of whose subsets sum to $\ge T^\*$. So if we feed $S$, $T^\*$ as input to $A'$, $A'$ will return a collection of size at least $k$. But $\tilde{T}$ is the maximal such $T$, so $\tilde{T} \ge T^\*$.

We know that $\tilde{T} = T^\*$ lies between $T=1$ and $T=\lfloor (\sum\_{a\_i \in S} a\_i) / k \rfloor \le m\_1a + m\_2b$.

So to find $\tilde{T}$, we need only $O(\log(m\_1a + m\_2b))$ calls to $A'$ with binary search: any $T$ for which we get a collection of size $\ge k$ from $A'$ is $\le \tilde{T}$; any $T$ for which we get a collection of size $< k$ from $A'$ is $> \tilde{T}$. $\square$

Now we show (or \*claim to show\*) that $P'$ can be solved in poly-time:

---

**Problem $P'$**: given a multiset $S$ of $m\_1$ elements equal to $a \in \mathbb{Z}^+$ and $m\_2$ elements equal to $b \in \mathbb{Z}^+$, and $T \in \mathbb{Z}^+$, what is the maximally sized disjoint collection of subsets of $S$ which has the property that each subset's sum is $\ge T$?

**Claim 2** we can solve $P'$ in poly-time.

Let $\ell^\*$ denote the size maximal size disjoint collection (we are looking for $\ell^\*$ and a disjoint collection that achieves this maximum).

*First some definitions*:

**Definition** call multisets consisting of only $a$'s and $b$'s, "$(a, b)$-multisets". Any such multiset can be identified by an ordered pair $(i, j)$ where $i$ denotes the number of $a$'s and $j$ denotes the number of $b$'s.

**Definition** "$(a,b,T)$-minimal multisets" $(i, j)$ are those $(a,b)$-multisets for which removing any element would bring you to a sum below $T$: i.e. $ai + bj \ge T$, but $a(i-1) + bj < T$ and $ai + b(j-1) < T$. For example, if $a=2$ and $b=5$ and $T=20$, the minimal multisets would be $(10, 0)$, $(8, 1)$, $(5, 2)$, $(3, 3)$ and $(0, 4)$.

*Observation*: Without loss of generality, we can assume that the optimal collection of $\ell^\*$ subsets of $S$ consists of only $(a, b,T)$-minimal multisets. To see why this is without loss of generality, consider any collection of $\ell^\*$ subsets of $S$, each with sum $\ge T$: remove as many elements as you can from each of these subsets, while maintaining the invariant that each must have sum $\ge T$. Once you cannot remove any more, you have a collection of $\ell^\*$ $(a,b,T)$-minimal subsets. So indeed it is fine to look only for collections of $(a,b,T)$-minimal multisets.

Note that there are not so many "minimal" $(a,b,T)$-multisets that can be subsets of $S$: we can crudely bound by $\min(m\_1, m\_2)+1$ (since no two minimal multisets can have either coordinate equal).

Call the actual number of these minimal multisets that are also subsets of $S$ as $M$. Order these $M$ subsets in say lexicographically decreasing order (like we did above), and call them $(i\_1, j\_1), (i\_2, j\_2), \dots, (i\_p, j\_p),\dots, (i\_M, j\_M)$.

We claim to solve $P'$ in poly-time with a dynamic programming approach (where we'll construct the optimal $\ell^\*$ minimal multisets in lexicographically decreasing order):

Our overall problem is to compute the maximum number of disjoint $(i\_p, j\_p)$s we can find among the base set $S = (m\_1, m\_2)$.

Let $F(M', m\_1', m\_2')$ be defined as the maximally sized disjoint collection of $(m\_1', m\_2')$ you can find, where all the subsets must be one of the lexicographically smallest $M'$ subsets of the $M$ $(a,b,T)$-minimal subsets we identified, i.e. $(i\_{M-M'+1}, j\_{M-M'+1}), (i\_{M-M'+2}, j\_{M-M'+2}) ..., (i\_M, j\_M)$.

We want to find $F(M, m\_1, m\_2)$.

We have the recurrence $$F(M, m\_1, m\_2) = 1 + \max\_{p=1, 2, \dots, M} F(M-p+1, m\_1-i\_p, m\_2-j\_p)$$ and similarly $$F(M', m\_1', m\_2') = 1 + \max\_{p=M-M'+1, \dots, M} F(M-p+1, m'\_1-i\_p, m'\_2-j\_p).$$ In each subproblem none of the 3 coordinates ever increase, and always either $m\_1'$ or $m\_2'$ decreases.

The running time of this dynamic programming is bounded by $O(M (Mm\_1m\_2)) = O((m\_1+m\_2)^4)$, as we wanted (strictly, the DP only gives the value of $\ell^\*$ and not an achieving disjoint $\ell^\*$-collection, but I think an actual optimal solution should be able to be constructed from the DP table as well). $\square$.

> **Comments:**
> **username_0**: Thank you for the answer. I have one question regarding the Observation. When $T$ is small, it is possible that the value of the minimum-valued subset in the optimal partition of $S$ is well beyond $T$. In this case, we cannot say that all the subsets are minimal as you defined.  
> **username_1**: I admittedly had not thought specifically about this case, but the observation should still hold. "Minimal" subsets for $T$ are defined in reference to a particular $a$, $b$.    Like if $a$ and $b$ are both larger than $T$, then by definition the "minimal" $(a, b)$-subsets are the singleton sets $\{a\}$ and $\{b\}$, and the optimally large collection of $\ell$ subsets of $S$ is the partition of $S$ into singletons.    If $a < T < b$, then there are 2 minimal subsets: $\{b\}$ and the set consisting of $\lceil T / a \rceil$ copies of $a$.  
> **username_0**: My point was that for certain values of $T$, the total number of items in the union of $\ell$ minimal subsets w.r.t. $T$ need not equal $m$, the total number of items. Perhaps you could clarify what you mean by "maximally sized collection of ℓ of disjoint subsets of S" in your definition of $P'$. Thank you!  
> **username_1**: Oh hm. So $P'$ is a problem where given some $T$, you want to find as many disjoint subsets of $S$ as possible that have sum $\ge T$. It's sort of a "dual" problem to $P$, informally speaking.  A "collection of $\ell$ [of] disjoint subsets of $S$" (second "of" should be deleted) is similar to an $\ell$-partition of $S$, except that the union of the $\ell$ subsets need not be equal to the full $S$ [there can be some "leftover" elements of $S$].  So I see now you are right that the observation as stated is wrong (but a close relative, which is what I sort of meant, is right - contd)...  
> **username_1**: Let $\ell^*$ denote the optimal value. My claim is that given any optimal collection -- i.e. any collection of $\ell^*$ subsets of $S$ each of whose sum is $\ge T$, you can easily transform this into a collection of $\ell^*$ "minimal" subsets of $S$ as follows: for any subset, just remove elements and put them into the "leftover" pile until you can no longer remove elements. You're now left with $\ell^*$ "minimal" subsets. This establishes that we're ok to only search of collections of "minimal" subsets, rather than any possible collection of subsets, so the rest proceeds the same.  
> **username_1**: But this sentence -- "Any optimal collection of ℓ subsets of our multiset  [aka (1,2)], can be assumed to consist of "minimal" (,)-multisets" -- is not true; will plan to edit this (I do still think the proof overall still works though).  I'm not sure if this addresses your exact concerns -- I don't know if I'm fully understanding the latest one -- but yeah.  
> **username_1**: Additionally: if relevant, some detail on reduction from from $P$ to $P'$: suppose for some $T$, $P'$ returns a collection of size at least $k$ -- then certainly you can find a $k$-partition of $S$ with each subset summing to $\ge T$ (you can throw the "leftover" elements into any other set, and now it's a partition).  If for some $T$, $P'$ returns a collection of size $< k$ -- this means there is no collection of $k$ disjoint subsets of $S$, and in particular no $k$-partition, with each subset having sum $\ge T$.  So reduction from $P$ to $P'$ should work.  
> **username_1**: Edited a bunch, going off of these comments.  

---

### Answer by username_2 on 2021-03-30. Score: 0

The standard pseudo-polynomial time algorithm for the partition problem with a slight change solves this problem in polynomial time.

The difference with the standard subset-sum or partition problem is the following: for the subset sum problem, to achieve a value $T$, you have to examine $T$ values of the corresponding table, however, in this case, all we have to do is to examine $O(n^2)$ values. Since if $T=i\cdot a + j\cdot b$ (assuming $T$ is a round number and it can be written in this form, otherwise, it is possible to change the algorithm), there are at most $n$ occurrences of $a$ and at most $n$ occurrences of $b$ (assuming the multiset has $n$ members), you have to check at most $n^2$ values to obtain $T$ (instead of $T$ values). Generally speaking, if there are $d$ different values, we have to check at most $n^d$ values for $T$ (this is just a very naive approach though, there might be faster approaches, like $f(d) Poly(n)$ checks). Note that the standard pseudo-polynomial-time algorithm for the $2$-partition problem extends to the one that has to partition the input into $k$ sets of (almost) equal sizes, and as long as $k$ is a constant, [it gives a pseudopolynomial time algorithm](https://en.wikipedia.org/wiki/Multiway_number_partitioning#Exact_algorithms); in the case that number of possible values is limited, this is a polynomial-time algorithm.

However, there is a catch here. In your question, the input is given as a real multiset with all its elements and you asked to be polynomial w.r.t. that input size, however, the multiset can be represented by only $4$ numbers $a,b,i,j$: $i$ determines how many $a$'s are in the multiset and $j$ determines how many $b$'s are in the multiset. In this case, the above approach has to still examine $O(i\cdot j)$ values, but the input size is $O(\log (a+b+i+j))$, which means that if e.g. $i>>\log (a+b)$ the above algorithm is not necessarily polynomial-time anymore. I don't know if it is possible to solve this problem in $Poly (\log (a+b+i+j))$.


---

