patternMinor
Bounded bin covering problem
Viewed 0 times
boundedproblemcoveringbin
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#62591, answer score: 3
Revisions (0)
No revisions yet.