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+ε)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1/ε, i.e., Ω ( n 2 2 1/ε ). A double or triple exponential dependence on 1/ε 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+ε)-approximation algorithm with a running time of O ε (1)⋅ n O (1) . In particular, the exponent of n in the running time does not depend on ε 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 Ω (2 2 1/ε ) 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 Ω ( n 2 2 1/ε ) and we improve both to O ε (1)⋅ n O (1) . We complete our result by giving an algorithm for two-dimensional knapsack for rectangles under (1+ε)-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.

We study the two-dimensional geometric knapsack problem, in which we are given a set of n axis-aligned rectangular items, each one with an associated profit, and an axis-aligned square knapsack. The goal is to find a (non-overlapping) packing of a maximum profit subset of items inside the knapsack (without rotating items). The best-known polynomial-time approximation factor for this problem (even just in the cardinality case) is 2+ε [Jansen and Zhang, SODA 2004]. In this article we present a polynomial-time 17/9+ε < 1.89-approximation, which improves to 558/325+ε < 1.72 in the cardinality case. Prior results pack items into a constant number of rectangular containers that are filled via greedy strategies. We deviate from this setting and show that there exists a large profit solution where items are packed into a constant number of containers plus one L-shaped region at the boundary of the knapsack containing narrow-high items and thin-wide items. These items may interact in complex manners at the corner of the L. The best-known approximation ratio for the subproblem in the L-shaped region is 2+ε (via a trivial reduction to one-dimensional knapsack); hence, as a second major result we present a PTAS for this case that we believe might be of broader utility. We also consider the variant with rotations, where items can be rotated by 90 degrees. Again, the best-known polynomial-time approximation factor (even for the cardinality case) is 2+ε [Jansen and Zhang, SODA 2004]. We present a polynomial-time (3/2+ε)-approximation for this setting, which improves to 4/3+ε in the cardinality case.

An important question in theoretical computer science is to determine the best possible running time for solving a problem at hand. For geometric optimization problems, we often understand their complexity on a rough scale, but not very well on a finer scale. One such example is the two-dimensional knapsack problem for squares. There is a polynomial time (1 + ∊)-approximation algorithm for it (i.e., a PTAS) but the running time of this algorithm is triple exponential in 1/e, i.e., A double or triple exponential dependence on 1/e is inherent in how this and several other algorithms for other geometric problems work. In this paper, we present an EPTAS for knapsack for squares, i.e., a (1+∊)-approximation algorithm with a running time of O∊(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 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 Ω(221/∊) 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 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 + ∊)-resource augmentation. In this setting, we also improve the best known running time of Ω(n1/∊) to O∊(1) nO(1), and compute even a solution with optimal profit, in contrast to the best previously known polynomial time algorithm for this setting that computes only an approximation. We believe that our new techniques have the potential to be useful for other settings as well.

In the online bin packing problem, items of sizes in (0,1] arrive online to be packed into bins of size 1. The goal is to minimize the number of used bins. Harmonic++ achieves a competitive ratio of 1.58889 and belongs to the Super Harmonic framework [Seiden, J. ACM, 2002]; a lower bound of Ramanan et al. shows that within this framework, no competitive ratio below 1.58333 can be achieved [Ramanan et al., J. Algorithms, 1989]. In this paper, we present an online bin packing algorithm with asymptotic performance ratio of 1.5815, which constitutes the first improvement in fifteen years and reduces the gap to the lower bound by roughly 15%. We make two crucial changes to the Super Harmonic framework. First, some of the decisions of the algorithm will depend on exact sizes of items, instead of only their types. In particular, for item pairs where the size of one item is in (1/3,1/2] and the other is larger than 1/2 (a large item), when deciding whether to pack such a pair together in one bin, our algorithm does not consider their types, but only checks whether their total size is at most 1. Second, for items with sizes in (1/3,1/2] (medium items), we try to pack the larger items of every type in pairs, while combining the smallest items with large items whenever possible. To do this, we postpone the coloring of medium items (i.e., the decision which items to pack in pairs and which to pack alone) where possible, and later select the smallest ones to be reserved for combining with large items. Additionally, in case such large items arrive early, we pack medium items with them whenever possible. This is a highly unusual idea in the context of Harmonic-like algorithms, which initially seems to preclude analysis (the ratio of items combined with large items is no longer a fixed constant). For the analysis, we carefully mark medium items depending on how they end up packed, enabling us to add crucial constraints to the linear program used by Seiden. We consider the dual, eliminate all but one variable and then solve it with the ellipsoid method using a separation oracle. Our implementation uses additional algorithmic ideas to determine previously hand set parameters automatically and gives certificates for easy verification of the results. We give a lower bound of 1.5766 for algorithms like ours. This shows that fundamentally different ideas will be required to make further improvements