# A Box Decomposition Algorithm to Compute the Hypervolume Indicator

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2015.

## Built on by (most cited first, 9 of 9)

- [Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement](https://mlsanity.com/paper/2105.08195/) (2021)
- [Joint Entropy Search for Multi-objective Bayesian Optimization](https://mlsanity.com/paper/2210.02905/) (2022)
- [Robust Multi-Objective Bayesian Optimization Under Input Noise](https://mlsanity.com/paper/2202.07549/) (2022)
- [qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson sampling](https://mlsanity.com/paper/2310.15788/) (2023)
- [PF2ES: Parallel Feasible Pareto Frontier Entropy Search for Multi-Objective Bayesian Optimization](https://mlsanity.com/paper/2204.05411/) (2022)
- [Knowledge Gradient for Multi-Objective Bayesian Optimization with Decoupled Evaluations](https://mlsanity.com/paper/2302.01310/) (2023)
- [What if we Increase the Number of Objectives? Theoretical and Empirical Implications for Many-objective Optimization](https://mlsanity.com/paper/2106.03275/) (2021)
- [Multi-objective optimization via equivariant deep hypervolume approximation](https://mlsanity.com/paper/2210.02177/) (2022)
- [Approximation of Box Decomposition Algorithm for Fast Hypervolume-Based Multi-Objective Optimization](https://mlsanity.com/paper/2512.05825/) (2025)

## Abstract (arXiv)

We propose a new approach to the computation of the hypervolume indicator, based on partitioning the dominated region into a set of axis-parallel hyperrectangles or boxes. We present a nonincremental algorithm and an incremental algorithm, which allows insertions of points, whose time complexities are O(n^lfloor fracp-12 rfloor+1) and O(n^lfloor fracp2 rfloor+1), respectively. While the theoretical complexity of such a method is lower bounded by the complexity of the partition, which is, in the worst-case, larger than the best upper bound on the complexity of the hypervolume computation, we show that it is practically efficient. In particular, the nonincremental algorithm competes with the currently most practically efficient algorithms. Finally, we prove an enhanced upper bound of O(np-1) and a lower bound of Omega (n^lfloor fracp2rfloor log n ) for p ≥ 4 on the worst-case complexity of the WFG algorithm.