3
$\begingroup$

This all seems fairly related to the knapsack problem, bin packing and the subset sum problem, but I can't find the appropriate problem name.

I have a multiset $S$ of $n$ (not necessarily unique) integers in the range $\{1,2,\dots,k-1\}$.

The problem is to partition this multiset in submultisets such that each submultiset has a sum of at least $s$ and the number of submultisets is maximized.

For example $k=20 \wedge s=40 \wedge S= \{14, 19, 12, 19, 3,15\} \Rightarrow \{\{19, 19, 3\}, \{12, 14, 15\}\}$.

Is this a known problem? What is its complexity, considering $s, k$ are bounded small integers?

$\endgroup$
  • $\begingroup$ @Raphael For the record, this is not homework, just personal interest. My google-fu is lacking here, I just don't seem to hit any results that attempt to maximize the number of subsets. As for attempting to devise an algorithm myself it seems inevitable that it comes from the corner of dynamic programming and will look a lot like one of the standard algorithms with some different predicate, but haven't thought much more deeply than that. $\endgroup$ – orlp Aug 14 '16 at 18:40
  • $\begingroup$ @Raphael After some more googling I finally uncovered 'bin covering', which seems to describe this problem fairly well. However I still haven't found any literature that studies the bounded integer case. $\endgroup$ – orlp Aug 14 '16 at 18:56
  • $\begingroup$ Instead of a fast algorithm, you should consider a reduction from subset sum (or look at the "standard" reduction from 3-SAT to subset sum, and work from there). $\endgroup$ – Juho Aug 14 '16 at 19:27
  • $\begingroup$ @Juho Subset sum is linear time if the sum is a small constant though ($O(sN)$), which is the case for my problem. $\endgroup$ – orlp Aug 14 '16 at 19:47
3
$\begingroup$

When $k,s$ are upper-bounded by a constant, the problem can be solved in polynomial time.

Call a multiset $T$ good if its sum is at least $s$, and if removing any one element causes the sum to fall strictly below $s$, and if all elements are in the set $\{1,2,\dots,k-1\}$. How many good multisets are there? Well, since $k$ and $s$ are constants, the number of such multisets is also a constant. (A very crude upper bound is $k^s$, which is a constant.)

Let's write down an integer linear program that is equivalent to your problem. We'll have an integer variable $x_T$ for each good multiset $M$, constrained so that $x_T \ge 0$. The idea is that $x_T$ will count the number of times $T$ appears in the partition that constitutes the solution to your problem. We obtain $k-1$ linear equations of the form

$$\sum_T m_T(i) x_T = m_S(i)$$

for each $i \in \{1,2,\dots,k-1\}$, where $m_T(i)$ denotes the multiplicity of $i$ in $T$. Now our goal is to maximize $\sum_T x_T$, the number of multisets in the resulting partition.

Thus, we obtain an integer linear program in constant dimension: i.e., it has (at most) a constant number of variables and (at most) a constant number of linear inequalities. It is known that integer linear programming in constant dimension can solved in polynomial time. Therefore, your problem can be solved in polynomial time, too.


Of course, this doesn't necessarily mean the algorithm will be efficient in practice. The constants that are hidden by asymptotic analysis are potentially huge.


As a side note, if $k,s$ are part of the input (not fixed) and all integers are provided in binary, the problem is NP-hard. The special case where $s = \frac12 \sum_{i \in S} i$ is equivalent to the partition problem, which is NP-complete so your problem is NP-hard as well, assuming $k$ is part of the input. So your promise that $k,s$ are upper-bounded by a constant makes a crucial difference to the complexity of your problem.

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