This post shows how to solve the special case for this problem. The special case has exactly one bin, and each ball have weight a power of $2$. It is one of the most popular unanswered problem on cs.stackexchange as of writing.

In fact, we do not require the $w_i$s are powers of $2$. We can establish polynomial time as long as $w_{i+1}/w_i$ is bounded by a polynomial in terms of the input size for all $i$. However, for simplicity of exposition, assume $w_i$s are powers of $2$. We do not know the case when $w_{i+1}/w_i$ is unbounded.

Consider a more natural problem without the absolute values.

We show Problem 1 reduces to Problem 2 with polynomial blow up, and Problem 2 can be solved in polynomial time.

1 Reduction

The reduction goes through a few steps. We start with the integer program in [Problem 1], and let $y_i=a_i-x_i$, and we get

$$\begin{array}{rl}\text{Minimize:}& \sum _{i=1}^n|y_i|\\ \text{subject to:}& \sum _{i=1}^n{w}_i{y}_i=\sum _{i=1}^n{w}_i{a}_i-c\\ & a_i-b_i\le y_i\le a_i\text{ for all }1\le i\le n\end{array}$$

Let $c^{\prime }={\sum }_{i=1}^n{w}_i{a}_i-c$, and $l_i=a_i-b_i$ and $u_i=a_i$.

$$\begin{array}{rl}\text{Minimize:}& \sum _{i=1}^n|y_i|\\ \text{subject to:}& \sum _{i=1}^n{w}_i{y}_i=c^{\prime }\\ & l_i\le y_i\le u_i\text{ for all }1\le i\le n\end{array}$$

Let $y_i=y_i^{+}-y_i^{-}$, where $y_i^{-},y_i^{+}\ge 0$, we can remove the absolute value.

$$\begin{array}{rl}\text{Minimize:}& \sum _{i=1}^n{y}_i^{+}+y_i^{-}\\ \text{subject to:}& \sum _{i=1}^n{w}_i{y}_i^{+}+\sum _{i=1}^n-w_i{y}_i^{-}=c^{\prime }\\ & l_i\le y_i^{+}-y_i^{-}\le u_i\text{ for all }1\le i\le n\\ & y_i^{-},y_i^{+}\ge 0\text{ for all }1\le i\le n\end{array}$$

Observe that we can separate the inequalities involving $y_i^{+}-y_i^{-}$, because there is always an optimal where $y_i^{-}$ or $y_i^{+}$ is $0$.

$$\begin{array}{rl}\text{Minimize:}& \sum _{i=1}^n{y}_i^{+}+y_i^{-}\\ \text{subject to:}& \sum _{i=1}^n{w}_i{y}_i^{+}+\sum _{i=1}^n-w_i{y}_i^{-}=c^{\prime }\\ & 0\le y_i^{+}\le u_i\text{ for all }1\le i\le n\\ & 0\le y_i^{-}\le -l_i\text{ for all }1\le i\le n\end{array}$$

This is an integer program as a bounded exact knapsack problem.

$$\begin{array}{rl}\text{Minimize:}& \sum _{i=1}^n{x}_i\\ \text{subject to:}& \sum _{i=1}^n{w}_i{x}_i=c\\ & 0\le x_i\le b_i\text{ for all }1\le i\le n\end{array}$$

Finally, apply the standard technique that rewrites a bounded knapsack problem to $0$-$1$-knapsack problem (see Section 7.1.1 of [1]). The blow up in problem size is at most a factor of $O(\log {\max }_i{b}_i)$. We can get the integer program in Problem 2, and also the weights are all powers of $2$. The reduction runs in polynomial time with respect to input size.

2 Solving Problem 2

Yuzhou Gu noted that the integer program in Problem 2 has a dynamic programming solution.

Let $D[m,k]$ to be the optimal value to the following problem

$$\begin{array}{rl}\text{Minimize:}& \sum _{j=1}^m{c}_j{x}_j\\ \text{subject to:}& \sum _{j=1}^m{w}_j{x}_j=k|w_m|+t\mathrm{mod}|w_m|\\ & x_j\in \{0,1\}\text{ for all }1\le j\le m\end{array}$$

The claim is that $D[m,k]$ can be expressed by the following recurrence relation.

$$D[m,k]=\underset{x_m\in \{0,1\}}{\min }D\left[m-1,\frac{|w_m|k-w_m{x}_m+(t\mathrm{mod}|w_m|-t\mathrm{mod}|w_{m-1}|)}{|w_{m-1}|}\right]$$

Note that $|k|$ is at most $m$. Therefore the table has at most $O(n^2)$ entries. To obtain the solution to the original equation, we find the minimum overall $D[n,k]$. Clearly, this runs in polynomial time.

References