Treffer: Approximating Geometric Knapsack via L-packings.

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 bestknown 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. [ABSTRACT FROM AUTHOR]

Copyright of ACM Transactions on Algorithms is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)