Anchored rectangle and square packings

The above constructive lower bounds immediately yield constant-factor approximations, of 7∕12−ε for rectangles and 5∕32 for squares, for computing anchored packings of maximum area in O(nlogn) time. We prove that a simple greedy strategy achieves a 9∕47-approximation for anchored square packings, and 1∕3 for lower-left anchored square packings. Reductions to maximum weight independent set (MWIS) yield a QPTAS for anchored rectangle packings in exp(poly(ε−1logn)) time and a PTAS for anchored square packings in nO(1∕ε) time.