Two valued variant of subset sum problem

Question

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!

Answer 1

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

Answer 2

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