NFDH algorithm

Dependencies:

  1. Geometric packing problems (BP, KS, SP) and rvol

Next-Fit Decreasing Height (NFDH) is an algorithm for 2D geometric bin packing and strip packing. It sorts items in decreasing order of height and packs them into 'shelves'. See section 1.5 in [bansal2009structural] for a complete description of the algorithm.

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. PTAS for 2D geometric density-restricted knapsack
  2. 2D BP: NFDH for items of small width
  3. 2D BP: NFDH for small items
  4. 2D BP: NFDH for items of small height
  5. 2D BP: NFDH(I) ≤ 4⌈rvol(I)⌉ + 1
  6. 2D SP: NFDH(I) < 2rvol(I) + hmax
  7. 2D SP: NFDH(I) < a(I)/(W-ε) + hmax for ε-small items
  8. NFDH: area of adjacent bins

Info:

Transitive dependencies:

  1. Bin packing and Knapsack
  2. Geometric packing problems (BP, KS, SP) and rvol