Approximating geometric knapsack via l-packings

Abstract

We study the two-dimensional geometricknapsack problem (2DK) in which we are given a setofnaxis-aligned rectangular items, each one with anassociated profit, and an axis-aligned square knapsack. Thegoal is to find a (non-overlapping) packing of a maximumprofit subset of items inside the knapsack (without rotatingitems). The best-known polynomial-time approximationfactor for this problem (even just in the cardinality case)is2+ε[Jansen and Zhang, SODA 2004]. In this paper webreak the2approximation barrier, achieving a polynomial-time179+ε <1.89approximation, which improves to558325+ε <1.72in the cardinality case.Essentially all prior work on2DKapproximation packsitems inside a constant number of rectangular containers,where items inside each container are packed using a simplegreedy strategy. We deviate for the first time from thissetting: we show that there exists a large profit solutionwhere items are packed inside a constant number ofcontainersplusone L-shaped region at the boundary of theknapsack which contains items that are high and narrowand items that are wide and thin. The items of these twotypes possibly interact in a complex manner at the cornerof theL.The above structural result is not enough however: thebest-known approximation ratio for the subproblem in theL-shaped region is2 +ε(obtained via a trivial reductionto one-dimensional knapsack by considering tall or wideitems only). Indeed this is one of the simplest specialsettings of the problem for which this is the best knownapproximation factor. As a second major, and the mainalgorithmic contribution of this paper, we present a PTASfor this case. We believe that this will turn out to be usefulin future work in geometric packing problems.We also consider the variant of the problemwithrotations(2DKR), where items can be rotated by90degrees. Also in this case the best-known polynomial-timeapproximation factor (even for the cardinality case) is2+ε [Jansen and Zhang, SODA 2004]. Exploiting part of the machinery developed for 2DK plus a few additional ideas, we obtain a polynomial-time 3=2 + "-approximation for 2DKR, which improves to 4=3+" in the cardinality case.