1
$\begingroup$

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!

$\endgroup$
1
  • $\begingroup$ 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\}$. $\endgroup$ – ashtavakra Mar 25 at 2:39
0
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ – ashtavakra Mar 28 at 16:43
  • $\begingroup$ 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$. $\endgroup$ – xmq Mar 28 at 19:53
  • $\begingroup$ 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! $\endgroup$ – ashtavakra Mar 30 at 0:10
  • $\begingroup$ 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)... $\endgroup$ – xmq Mar 30 at 2:02
  • $\begingroup$ 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. $\endgroup$ – xmq Mar 30 at 2:07
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.