1
$\begingroup$

Let's start with a set of positive integers $\{x_1,x_2,x_3,...,x_n\}$. My goal is to split it into $N$ subsets, such that:

  1. the sum of each subset is at least $S$, and
  2. $N$ is maximized.

How could I do this?

(Perhaps it is somehow related to the subset-sum problem?)

Added Nov 2, 2015

Context:

(I am not sure the context is relevant here but since the moderators ask for it.)

In a statistical problem I am trying to tackle, the total sample size $M$ is too big to be handled in one go. Fortunately, there exists natural grouping of the $M$ data points into $n$ smaller groups, each with size ${x_1,x_2,...,x_n},\sum_i x_i=M$ But then some groups have too few points to make the analysis statistically stable, so I want to form larger groups by combining these small groups, hence the question above.

The closest thing that come up in my search is the subset-sum problem.

Program-wise, of course I can do a brute-force search (keep combining and check if all groups are at least size $S$), but then I might not reach the optimal grouping (which maximizes $N$). I imagine some sort of integer-programming would yield the result but I wonder if there is a straight-forward algorithm.

$\endgroup$
  • $\begingroup$ Yes, this seems much like a subset-sum or knapsack problem, the difference being you have a lower bound on the size of pooled data sets rather than an upper bound (capacity). Therefore the theoretical complexity of such problems is likely NP-hard, but practical methods for approximating the maximum $N$ are perhaps known. For discussion of related statistical aspects, CrossValidated.SE is worth a look, for example this Question. $\endgroup$ – hardmath Nov 2 '15 at 12:26
  • $\begingroup$ Perhaps you have a "real-world" list of $x_i's$ and threshold $S$ that you'd like to give as an example? $\endgroup$ – hardmath Nov 4 '15 at 4:18
1
$\begingroup$

Yes, this can be formulated as a 0-1 (binary) integer programming problem, though that does not mean it necessarily has an efficient solution. It is known in the literature as the bin covering problem, e.g. Two simple algorithms for bin covering (1999), in contrast to the more commonly studied bin packing problem.

The first thing to note is that, with the objective of maximizing $N$ the number of parts in your partition of the data sets $\{1,\ldots,n\}$, any data sets for which $x_i \ge S$ should be assigned to separate parts by themselves. Thus without loss of generality, all $x_i \lt S$ and $S \gt M = \sum_{i=1}^n x_i$.

An obvious upper bound on the feasible $N$ is $U = \lfloor M/S \rfloor$. Therefore determining the maximum feasible $N$ is not more difficult than $\log_2 U$ times the complexity of a decision problem for particular $N \le U$.

The special case $N=2$ with $S = M/2$ is called the partition problem, and a pseudo-polynomial time algorithm based on dynamic programming is known. Perhaps surprisingly the case $N=3$ and $S = M/3$ seems to be more difficult, with no pseudo-polynomial algorithm unless P=NP.

The paper by Csirik et al linked in the first paragraph gives algorithms that construct bin coverings in linear or near-linear time in $n$, with proven performance ratios. That is, depending on the algorithm, achieving half, two-thirds, or three-quarters of the maximum $N$ "bins" covered. These constructions can be viewed both as lower bounds (achieved) and upper bounds (by the respective performance ratios).

Further developments by Csirik et al are found in Better Approximation Algorithms for Bin Covering (2000). The approach there is polished by Jansen and Solis-Oba (2003) in An asymptotic fully polynomial time approximation scheme for bin covering.

$\endgroup$
  • $\begingroup$ 'bin-covering' it is. The linked paper (i have only read the 1999 one) is helpful. thanks. $\endgroup$ – qoheleth Nov 4 '15 at 4:49

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.