There are $n$ bins and $m$ type of balls. The $i$th bin has labels $a_{i,j}$ for $1\leq j\leq m$, it is the expected number of balls of type $j$.

You start with $b_j$ balls of type $j$. Each ball of type $j$ has weight $w_j$, and want to put the balls into the bins such that bin $i$ has weight $c_i$. A distribution of balls such that previous condition holds is called a feasible solution.

Consider a feasible solution with $x_{i,j}$ balls of type $j$ in bin $i$, then the cost is $\sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}|$. We want to find a minimum cost feasible solution.

This problem is clearly NP-hard if there is no restriction on $\{w_j\}$. The subset sum problem reduces to the existence of a feasible solution.

However, if we add the condition that $w_j$ divides $w_{j+1}$ for every $j$, then the subset sum reduction no longer works, so it's not clear whether the resulting problem remains NP-hard. Checking for the existence of a feasible solution takes only $O(n\,m)$ time (attached at the end of the question), but this does not give us the minimum-cost feasible solution.

The problem has an equivalent integer program formulation. Given $a_{i,j},c_i,b_j,w_j$ for $1\leq i\leq n,1\leq j\leq m$: \begin{align*} \text{Minimize:} & \sum_{i=1}^n \sum_{j=1}^m |a_{i,j}-x_{i,j}| \\ \text{subject to:} & \sum_{j=1}^m x_{i,j}w_j = c_i \text{ for all } 1\leq i\leq n\\ & \sum_{i=1}^n x_{i,j} \leq b_j \text{ for all } 1\leq j \leq m\\ & x_{i,j}\geq 0 \text{ for all } 1 \leq i\leq n, 1\leq j \leq m\\ \end{align*}

My question is,

Is the above integer program NP-hard when $w_j$ divides $w_{j+1}$ for all $j$?

An algorithm to decide if there is a feasible solution in $O(n\,m)$ time:

Define $w_{m+1}=w_m(\max_{j} c_j + 1)$ and $d_j = w_{j+1}/w_j$. Let $a\%b$ be the remainer when $a$ is divided by $b$.

  1. If there exists a $c_i$ that's not divisible by $w_1$, return "no feasible solution". (the invariant $c_i$ divides $w_j$ will always be maintained in the following loop)
  2. for $j$ from $1$ to $m$:

    1. $k \gets \sum_{i=1}^n (c_i/w_j)\%d_j$. (the minimum of balls of weight $w_j$ required)
    2. If $b_j<k$, return "no feasible solution".
    3. $c_i \gets c_i - ((c_i/w_j)\% d_j)$ for all $i$. (remove the minimum number of required balls of weight $w_j$)
    4. $b_{j+1} \gets \lfloor (b_j-k)/d_j \rfloor$. (group smaller balls into a larger ball)
  3. return "there is a feasible solution".

A polynomial time solution to the special case where $n=1$, and $w_j$ are power of $2$s

It is known that if $n=1$ and all $w_j$ are powers of $2$, then this special case can be solved in polynomial time. \begin{align*} \text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\ \text{subject to:} & \sum_{j=1}^m w_j x_j = c\\ & 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\ \end{align*}

The solution was hinted at by Yuzhou Gu, and a write up may be found here.

  • 1
    $\begingroup$ I like the following formulation. You have a some coins that you need to use to make change for a group of $n$ customers, so that each customer $i$ receives coins with total value $c_i$. You have $m$ types of coins, in particular some $b_j$ coins of each type $j$, each having value $w_j$. Each customer $i$ wants to receive $a_{ij}$ coins of type $j$. Your goal is to minimize the total dissatisfaction of your customers, where the dissatisfaction of a customer $i$ is the sum, over the types $j$, of the difference between $a_{ij}$ and the number of coins of type $j$ s/he receives. $\endgroup$
    – Neal Young
    Commented Mar 13 at 17:38
  • 1
    $\begingroup$ We assume that $w_j$ is an integer multiple of $w_{j-1}$ (for $j\ge 2$), so that making change greedily always gives a feasible solution (if there is one). However, the greedy solution doesn't necessarily minimize dissatisfaction. $\endgroup$
    – Neal Young
    Commented Mar 13 at 17:43
  • $\begingroup$ @NealYoung This is very close to the original motivation. 10+ years ago, some friends and I had a night out at Flushing, and most establishments only take cash, and we were pooling our coins/notes to pay. We realize, 25c, \$1, \$5, \$10, \$20 gives us divisibility property and come up with: cs.stackexchange.com/questions/2648/… , which is very close to this problem (maybe it is the same problem in different form). Now days almost all Flushing places takes cards so this problem is less practical. $\endgroup$
    – Chao Xu
    Commented Mar 15 at 5:53

1 Answer 1


Some background. The above problem is the knapsack problem with restrictions. The most efficient knapsack problem solution with or without restrictions can be solved in pseudopolynomial time, still NP-Hard. For some variations, see https://en.wikipedia.org/wiki/Knapsack_problem#Definition. The first restriction in this variation is that the value of items (balls) to be placed in the knapsack (bins) does not matter. The problem is then restricted to the amount of time it takes to put the items in the knapsack. The original problem requires the most valuable items to be placed in as short amount of time possible. Another restriction with this version is that the weights and all other arguments are integers. And the restriction of interest is that the weights $w_j$ divide $w_{j+1}$ for all $j$. Note: the fractional knapsack problem can be solved in polynomial time, but does not present the most practical solutions to the original problem. This problem uses integers that divide evenly (no rational solutions). Perhaps see What's the big deal with the knapsack problem?.

The main question perhaps should be "is this problem still NP-Hard when $w_j$ is unbounded by a polynomial corresponding to $i$, as the problem is less complex (in P) when it is bounded? The reason I say this is because the problem can be shown to be in P when $w_j$ is bounded and NP-Hard when $w_j$ does not necessarily divide $w_{j+1}$ evenly (the weights are simply random), all restrictions limit the complexity of this problem to these two conditions. These conditions (1. the random weight knapsack problem without the item-value restriction and 2. divisible weight knapsack problem without the item-value restriction) negate each other in terms of reducing complexity, as the quotients of the weights may be random themselves (especially when unbounded), thus imposing exponential time calculations (this will be shown in the example below). Additionally, because $w_j$ divides $w_{j+1}$, $w_j$ increases in size exponentially for each $j$. This is because instead of using random weighted items (balls whose unit weight may all be limited to unit weights under 100 or 50 or even 10), the restriction instead causes the time complexity to depend on the number of digits of $w_j$, the same as trial division, which is exponential.

So yes, the above integer program remains NP-hard even when $w_j$ divides $w_{j+1}$ for all $j$. And this is easily observed.

Example 1: let $n = 1$ and $w_p$ be powers of two. Because of constant two, the entire problem is solved in quadratic time, as your example shows. The weights are not random and therefore the calculation is solved efficiently.

Example 2: let $w_{j+1}$ be defined as $w_j * p$, where $p$ is the prime number corresponding to $j$, such that $p=2, j=1: p=3, j=2, p=5, j=3, p=7, j=4,...,P, J$. This is applicable, as $w_j$ divides $w_{j+1}$ for all $j$. We get each $w_j$ is the product of all the primes up to $j$. The values of the unit weights increase as such: $1, 2, 6, 30, 210, 2310, 30030, ...$. Since there is a bound ($p_j$ ~ $j log (j)$, via the prime number theorem), as the quotients are all primes, we get the complexity NP-Intermediate.

Example 3: let $w_{j+1}$ be defined as $w_j * R_p$, where $R_p$ is a randomly chosen prime number from two to infinity, corresponding to $j$. This is applicable to this problem, as $w_j$ divides $w_{j+1}$ for all $j$. We get the first 5 quotients (randomly falling from two to infinity), as $101, 2657, 7, 3169, 2$. We see that even at the 5th ball, the weight has eleven digits. Fortunately, the fifth quotient was two and not a prime in the order of $10^{100}$ or larger.

Example three above is what happens when $w_j$ is not bounded (random weights) by a polynomial corresponding to $i$. The time complexity is exponential, NP-Hard. For some perspective, just add up all the weights, see if they fit. But there isn’t a solution to solving it significantly faster by making the weights divisible than trying each subset to see if it works. After a few dozen balls, you are still entering the realm of even the trillions of subsets or trillions of digits.

  • 1
    $\begingroup$ But prime factorization is considered not to be NP-hard. It is considered to be NP-indermediate. $\endgroup$
    – rus9384
    Commented Aug 5, 2017 at 1:20
  • 3
    $\begingroup$ I don't see a reduction here. What is the actual reduction? Taking input of prime factorization, and somehow output the factorization using solution of the integer program. $\endgroup$
    – Chao Xu
    Commented Aug 5, 2017 at 5:45
  • 3
    $\begingroup$ Would do you mean by "the above integer program is NP-hard"? An individual program cannot be NP-hard. $\endgroup$ Commented Aug 5, 2017 at 7:54
  • 1
    $\begingroup$ In fact prime factorization is in $\mathsf{NP\cap coNP}$. So, it is $\mathsf{NP}$-hard if $\mathsf{NP=coNP}$. $\endgroup$
    – rus9384
    Commented Aug 5, 2017 at 13:41
  • 2
    $\begingroup$ Unfortunately, the additional edits did not clear it up. An actual reduction would be helpful. $\endgroup$
    – Chao Xu
    Commented Aug 6, 2017 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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