The Art Gallery Guardian

Filling up a bin using balls with divisible weights


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 . It is one of the most popular unanswered problem on cs.stackexchange as of writing.

Problem1

We are interested in solving the following integer program, where each is a power of for all . Assume .

In fact, we do not require the s are powers of . We can establish polynomial time as long as is bounded by a polynomial in terms of the input size for all . However, for simplicity of exposition, assume s are powers of . We do not know the case when is unbounded.

Consider a more natural problem without the absolute values.

Problem2- exact knapsack problem with divisible weights

We are interested in solving the following integer program,

where for all . can be negative.

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 , and we get

Let , and and .

Let , where , we can remove the absolute value.

Observe that we can separate the inequalities involving , because there is always an optimal where or is .

Remark

This observation fails when the number of bins is more than .

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

Finally, apply the standard technique that rewrites a bounded knapsack problem to --knapsack problem (see Section 7.1.1 of [1]). The blow up in problem size is at most a factor of . We can get the integer program in Problem 2, and also the weights are all powers of . 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 to be the optimal value to the following problem

The claim is that can be expressed by the following recurrence relation.

Note that is at most . Therefore the table has at most entries. To obtain the solution to the original equation, we find the minimum overall . Clearly, this runs in polynomial time.

References

[1] H. Kellerer, U. Pferschy, D. Pisinger, Knapsack problems, Springer, 2004.

Posted by Chao Xu on .
Tags: optimization, integer.