Fast additive constant approximation algorithms for the safe deposit boxes problem with two and three currencies

The following variant of the knapsack problem is considered; Suppose there are n safe deposit boxes, each containing known amounts of m currencies, and there is a certain need for each currency. The problem is to open the minimal number of boxes, in order to collect at least the prescribed amount of each currency. In a technical report, by Y. Dinitz and A. Karzanov, it is shown that this problem is NP-hard, and that its non-degenerate case can be solved within an absolute error of at most m - 1 in O(n^m+1) time, assuming m is constant. They also suggested an O(n²) algorithm, with an absolute error of at most 1, for the general case of two currencies. We suggest new combinatorial algorithms with significantly improved runtime for the two and three currency cases (2D,3D). The 2D algorithm runs in O(nlog² n) time, while the 3D algorithm runs in O(n² log² n) time. In addition to linear programming techniques, used in previous works, we also use the parametric search approach of N. Megiddo [10] for decreasing the running time. The degenerate case is formulated as an interesting problem, solved by combinatorial techniques.