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:
- 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.
- 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:
- Stack containers: Items are stacked along one coordinate axis (height, width, or depth).
- Area containers: Items are packed along a single 2D face using Next-Fit-Decreasing-Height (NFDH), essentially ignoring the third dimension.
- Volume containers: Packed using 3D-NFDH for items small in all three dimensions.
- 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. - L-Containers: (Used when rotations are allowed) Two orthogonal stacks of items form an L-shape within the container cross-section.
- 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).
- 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