Improved Approximation Algorithms for Three-Dimensional Knapsack

Klaus Jansen, Debajyoti Kar, Arindam Khan, K. V. N. Sreenivas, Malte Tutas

TL;DR

This paper breaks a nearly 20-year stalemate in 3D geometric knapsack problems by presenting an improved $(139/29 + \varepsilon) \approx 4.794$-approximation algorithm (down from $7 + \varepsilon$). The authors introduce a versatile framework called container packing, which partitions the knapsack into a constant number of structured regions and solves the item assignment problem via the Generalized Assignment Problem (GAP).

What Problem Does This Paper Address?

In the Three-Dimensional Knapsack (3DK) problem, you are given a set of axis-aligned 3D cuboids (each with dimensions width, depth, height, and a profit value) and a unit-cube knapsack. The objective is to pack a non-overlapping, axis-aligned subset of these cuboids into the knapsack via translations to maximize total profit.

3DK is a core problem in logistics, cargo loading, and combinatorial optimization. However, it is notoriously hard: unlike 1D knapsack (which admits an FPTAS) and 2D geometric knapsack (approximable within $1.89$), 3DK does not even admit an asymptotic PTAS (APTAS), even when all item profits are identical. Since 2008, the best-known approximation factor stood at $7 + \varepsilon$ for general 3DK and $5 + \varepsilon$ when 90-degree rotations are permitted. Improving upon these bounds had remained an open question for almost two decades due to the complex, non-monotonic geometric interactions of 3D items.

Methods

The authors introduce container packing, a general paradigm bridging geometric packing and classical assignment algorithms:

  1. Knapsack Discretization & Guessing: The knapsack is partitioned into a constant ($O(1)$) number of rectangular sub-regions called containers, chosen from a polynomial-sized set of potential container dimensions.
  2. Container Types & Specialized Routines: Each container type is equipped with a capacity function, an item size function $f_C(i)$, and a polynomial-time packing subroutine $A_C$. The paper introduces six distinct container classes:
  3. Stack containers: Items are stacked along one coordinate axis (height, width, or depth).
  4. Area containers: Items are packed along a single 2D face using Next-Fit-Decreasing-Height (NFDH), essentially ignoring the third dimension.
  5. Volume containers: Packed using 3D-NFDH for items small in all three dimensions.
  6. Steinberg containers: Pack heterogeneous items using a novel algorithm called 3D-Vol-Pack, which groups items into layers and packs them using Steinberg's 2D packing algorithm.
  7. L-Containers: (Used when rotations are allowed) Two orthogonal stacks of items form an L-shape within the container cross-section.
  8. GAP Formulation: Finding the optimal assignment of items to containers is modeled as a Generalized Assignment Problem (GAP) with $O(1)$ knapsacks. This can be approximated to within $(1 - O(\varepsilon))$ using a polynomial-time approximation scheme (PTAS).
  9. Structural Restructuring: The core theoretical work proves that an optimal arbitrary packing ($\text{OPT}$) can be transformed into a valid container packing while retaining a provable fraction of its original profit.

Datasets

Not discussed in the paper. (This is a theoretical paper focusing on worst-case approximation algorithms and rigorous mathematical proofs.)

Key Insights and Ideas

  • Beyond Shelf and Greedy Packing: Previous 3D knapsack approaches relied heavily on simple shelf or stack packings. By integrating Steinberg’s 2D non-shelf packing into 3D volume-based layering (3D-Vol-Pack), the authors prove that any item collection small in height and bounded in width/depth can be packed up to a density of at least $1/3 - 2\varepsilon$.
  • Unified GAP Framework: Treating containers as bins in a Generalized Assignment Problem cleanly separates the geometric packing guarantees (handled by $A_C$ and capacity $f_C$) from the combinatorial item selection.
  • Intricate Volume-Profit Case Analysis: The authors classify items into large ($L$), thin ($I_1, I_2, I_3$), long, and small categories. By showing five distinct structural lower bounds on the profit capturable by container packings, they demonstrate that the worst-case scenario occurs only under extreme volume distributions ($v_1 \le 1/6$ and $v_{2s}, v_{3s} > 1/3$), yielding the factor $139/29 \approx 4.794$.

Key Results

The paper provides the first improvements in 17 years across several 3D knapsack variants:

Variant Previous Bound New Bound
General 3DK (no rotations) $7 + \varepsilon$ $\mathbf{\frac{139}{29} + \varepsilon \approx 4.794 + \varepsilon}$
3DK with $90^\circ$ Rotations (3DKR) $5 + \varepsilon$ $\mathbf{\frac{30}{7} + \varepsilon \approx 4.286 + \varepsilon}$
Cardinality Case (equal profits) $7 + \varepsilon$ $\mathbf{\frac{17}{4} + \varepsilon = 4.25 + \varepsilon}$ (no rot.) / $\mathbf{\frac{24}{7} + \varepsilon \approx 3.429 + \varepsilon}$ (rot.)
Uniform Profit-Density ($\text{Profit} = \text{Volume}$) $7 + \varepsilon$ $\mathbf{4 + \varepsilon}$ (no rot.) / $\mathbf{3 + \varepsilon}$ (rot.)

Limitations and Future Work

  • High Polynomial Runtime: The algorithm runs in time $n^{f(1/\varepsilon)}$ because it brute-force guesses the configuration of $O(1)$ containers and solves the resulting GAP instance.
  • Near-Linear Time: The authors suggest investigating whether recent dynamic and geometric techniques (such as those by Buchem, Deuker, and Wiese, 2024) can lower the runtime to $(n \cdot (\log n)^{f(1/\varepsilon)})$.
  • Tightness of Container Packing: Determining the true worst-case limit of container-based packings in 3D remains an intriguing open question.

Summary updated

Abstract

We study the three-dimensional Knapsack (3DK) problem, in which we are given a set of axis-aligned cuboids with associated profits and an axis-aligned cube knapsack. The objective is to find a non-overlapping axis-aligned packing (by translation) of the maximum profit subset of cuboids into the cube. The previous best approximation algorithm is due to Diedrich, Harren, Jansen, Thöle, and Thomas (2008), who gave a (7+ε)-approximation algorithm for 3DK and a (5+ε)-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant ε > 0. Chlebík and Chlebíková (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time (139/29+ε) ≈ 4.794-approximation algorithm for 3DK and (30/7+ε) ≈ 4.286-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case (when all items have the same profit) and uniform profit-density case (when the profit of an item is equal to its volume). Our key technical contribution is container packing - a structured packing in 3D such that all items are assigned into a constant number of containers, and each container is packed using a specific strategy based on its type. We first show the existence of highly profitable container packings. Thereafter, we show that one can find near-optimal container packing efficiently using a variant of the Generalized Assignment Problem (GAP).
BibTeX
@inproceedings{jansen2025improved,
  author = {Klaus Jansen and Debajyoti Kar and Arindam Khan and K. V. N. Sreenivas and Malte Tutas},
  title = {{Improved Approximation Algorithms for Three-Dimensional Knapsack}},
  booktitle = {SoCG},
  year = {2025},
  url = {https://openreview.net/forum?id=RDKQx54fVq},
}

Loading related content...

Figure