# Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization

arXiv: https://arxiv.org/abs/2512.05825 · HTML: https://mlsanity.com/paper/2512.05825/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 10 references that are in the map.
- First posted on arXiv 5 Dec 2025.

## Builds on (most cited first, 4 of 4)

- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [Differentiable Expected Hypervolume Improvement for Parallel Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2006.05078/) (2020)
- [A Box Decomposition Algorithm to Compute the Hypervolume Indicator](https://mlsanity.com/paper/1510.01963/) (2015)
- [Python Tool for Visualizing Variability of Pareto Fronts over Multiple Runs](https://mlsanity.com/paper/2305.08852/) (2023)

## Abstract (arXiv)

Hypervolume (HV)-based Bayesian optimization (BO) is one of the standard approaches for multi-objective decision-making. However, the computational cost of optimizing the acquisition function remains a significant bottleneck, primarily due to the expense of HV improvement calculations. While HV box-decomposition offers an efficient way to cope with the frequent exact improvement calculations, it suffers from super-polynomial memory complexity O(MN^lfloor fracM + 12 rfloor) in the worst case as proposed by Lacour et al. (2017). To tackle this problem, Couckuyt et al. (2012) employed an approximation algorithm. However, a rigorous algorithmic description is currently absent from the literature. This paper bridges this gap by providing comprehensive mathematical and algorithmic details of this approximation algorithm.