Options
2019
Journal Article
Titel
Faster approximation schemes for the two-dimensional knapsack problem
Abstract
For geometric optimization problems we often understand the computational complexity on a rough scale, but not very well on a finer scale. One example is the two-dimensional knapsack problem for squares. There is a polynomial time (1+e)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1/e, i.e., O (n221/e). A double or triple exponential dependence on 1/e is inherent in how this and other algorithms for other geometric problems work. In this article, we present an efficient PTAS (EPTAS) for knapsack for squares, i.e., a (1+e)-approximation algorithm with a running time of Oe(1)⋅ nO(1). In particular, the exponent of n in the running time does not depend on e at all! Since there can be no fully polynomial time approximation scheme (FPTAS) for the problem (unless P = NP), this is the best kind of approximation scheme we can hope for. To achieve this improvement, we introduce two new key ideas: We present a fast method to guess the O (221/e) relatively large squares of a suitable near-optimal packing instead of using brute-force enumeration. Secondly, we introduce an indirect guessing framework to define sizes of cells for the remaining squares. In the previous PTAS, each of these steps needs a running time of O (n221/e) and we improve both to Oe(1)⋅ nO(1). We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1+e)-resource augmentation. We improve the previous double-exponential PTAS to an EPTAS and compute even a solution with optimal weight, while the previous PTAS computes only an approximation.