Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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(nm)$ time(attached at the end of the question), but this does not give us the minimum-cost feasible solution.

The problem has a 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$?

It's not obvious how to solve this even when $n=1$ and $w_j=2^j$, namely \begin{align*} \text{Minimize:} & \sum_{j=1}^m |a_j-x_j| \\ \text{subject to:} & \sum_{j=1}^m 2^j x_j = c\\ & 0 \leq x_j \leq b_j \text{ for all } 1\leq j \leq m\\ \end{align*}

An algorithm to decide if there is a feasible solution in $O(nm)$ 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 remained of $a$ divides $b$.

  1. If there exist 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".
share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.