Improved Approximation Algorithms for Three-Dimensional Knapsack

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

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+\varepsilon)$-approximation algorithm for 3DK and a $(5+\varepsilon)$-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant $\varepsilon>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+\varepsilon) \approx 4.794$-approximation algorithm for 3DK and $(30/7+\varepsilon) \approx 4.286$-approximation when rotations by 90 degrees are allowed. We also provide improved approximation algorithms for several variants such as the cardinality case and uniform profit-density case. 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.

Introduction

The Three-Dimensional Knapsack (3DK) problem is a fundamental challenge in computational geometry and operations research. Given a set of axis-aligned cuboids (items) with varying profits and a single large cube (the knapsack), the goal is to pack a subset of items to maximize total profit without any overlaps. While the 1D version is a classic dynamic programming problem and the 2D version has seen steady progress, 3D packing is notoriously difficult due to the complex spatial interactions between items. For instance, an item might be "long" in one dimension but "tiny" in the other two, creating awkward gaps that are difficult to fill efficiently.

For nearly two decades, the state-of-the-art approximation ratios for this problem stood at 7 (without rotations) and 5 (with rotations). This paper breaks that stalemate by introducing a "container packing" framework, which partitions the knapsack into a constant number of structured regions to improve the approximation bounds significantly.

The Container Packing Framework

The core technical innovation of this work is the realization that any optimal packing, however chaotic, can be restructured into a highly structured "guessable" packing with only a marginal loss in total profit. This structured approach relies on three main steps:

1. Container Partitioning

The knapsack is divided into a constant number ($O(1)$) of rectangular regions called containers. By limiting the number of containers to a constant, the algorithm can "guess" the dimensions and positions of these containers in polynomial time.

2. Specialized Packing Strategies

Each container is assigned a specific "type" based on the geometric properties of the items it is intended to hold. These strategies include:

  • Stack Containers: Designed for items that can be piled simply one on top of another.
  • Area/Volume Containers: These utilize greedy heuristics such as Next-Fit-Decreasing-Height (NFDH) or its 3D variants to fill space efficiently.
  • Steinberg Containers: These use a sophisticated volume-based subroutine called 3D-Vol-Pack. This algorithm packs items in layers, where each layer is filled using either greedy methods or Steinberg’s classic 2D packing algorithm, providing tighter guarantees on utilized volume.
  • L-Containers: A specialized type introduced for the rotation-enabled variant of the problem to handle items that are large in two dimensions but small in the third.

3. Reduction to the Generalized Assignment Problem (GAP)

Because the number of container types and their possible dimensions are polynomially bounded, the problem of assigning items to these containers is reduced to a variant of the Generalized Assignment Problem (GAP). The authors leverage a Polynomial-Time Approximation Scheme (PTAS) for GAP to find the near-optimal assignment of items to the guessed containers.

Results and Analysis

The paper derives new, lower approximation ratios that hold for any possible input instance. The improvements are summarized in the table below:

Case Previous Best New Result (This Paper)
General (No Rotations) $7 + \epsilon$ $139/29 + \epsilon \approx 4.794$
General (With Rotations) $5 + \epsilon$ $30/7 + \epsilon \approx 4.286$
Cardinality (All profits = 1) - $4.25 + \epsilon$ (No Rot) / $3.429 + \epsilon$ (Rot)
Uniform Density (Profit = Volume) - $4 + \epsilon$ (No Rot) / $3 + \epsilon$ (Rot)

These results represent the first major progress on the 3DK approximation ratio in over 15 years. The "aha moment" of the research lies in the proof that a highly structured packing using only a few containers can capture a significant fraction of the optimal profit.

Limitations and Future Directions

Despite these improvements, the authors identify a theoretical "hardness" limit for the container-based framework. They demonstrate that no algorithm using a constant number of containers can achieve an approximation ratio better than 3. This suggests that reaching a $(2 + \epsilon)$ or $(1 + \epsilon)$ ratio will require entirely new, non-container-based techniques.

Furthermore, while the algorithms are polynomial in time, the constants involved in guessing container configurations and executing the GAP PTAS are high. As such, this work serves primarily as a theoretical breakthrough, establishing new upper bounds on the problem's complexity rather than providing a ready-to-use industrial packing solution. Future research may focus on extending this framework to other multidimensional scheduling and packing problems.

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\"{o}le, and Thomas (2008), who gave a $(7+\varepsilon)$-approximation algorithm for 3DK and a $(5+\varepsilon)$-approximation algorithm for the variant when the items can be rotated by 90 degrees around any axis, for any constant $\varepsilon>0$. Chleb\'{\i}k and Chleb\'{\i}kov\'{a} (2009) showed that the problem does not admit an asymptotic polynomial-time approximation scheme. We provide an improved polynomial-time $(139/29+\varepsilon) \approx 4.794$-approximation algorithm for 3DK and $(30/7+\varepsilon) \approx 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},
}
Figure