PTAS for 2D geometric density-restricted knapsack

Dependencies: (incomplete)

  1. Geometric packing problems (BP, KS, SP) and rvol
  2. NFDH algorithm
  3. 2D BP: NFDH for small items

Consider items in a 2D geometric knapsack problem. The density of an item is the ratio of its profit to its area. Let $\lambda$ be the ratio of the maximum density of an item to the minimum density of an item. If we only consider instances for which $\lambda$ is upper-bounded by a constant, then there is a PTAS for this variant of the knapsack problem (for both the rotational and non-rotational versions).

Proof can be found in section 3 of [bansal2009structural].

bansal2009structural
Bansal N, Caprara A, Jansen K, Prädel L, Sviridenko M.
A structural lemma in 2-dimensional packing, and its implications on approximability.
In International Symposium on Algorithms and Computation 2009 Dec 16 (pp. 77-86). Springer, Berlin, Heidelberg.

Dependency for:

  1. 2D BP: APTAS for config LP

Info:

Transitive dependencies:

  1. Bin packing and Knapsack
  2. Geometric packing problems (BP, KS, SP) and rvol
  3. NFDH algorithm
  4. 2D BP: NFDH for small items