On the complexity of computing the hypervolume indicator

Abstract

The goal of multi-objective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multi-objective optimizers providing them, unary quality measures are usually applied. Among these, the hypervolume indicator (or S-metric) is of particular relevance due to its good properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for searching the parameter space. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee s Measure Problem. In general, Klee s Measure Problem can be solved in O(n^d/2 log n) for an input instance of size n in d dimensions; as of this writing, it is unknown whether a lower bound higher than Omega(n log n) can be proven. In this article, we derive a lower bound of Omega(n log n) for the complexity of computing the hypervolume indicator in any number of dimensions d > 1 by reducing the problem to the so-called UNIFORMGAP problem. For the three dimensional case, we also present a matching upper bound of O(n log n) that is obtained by extending an algorithm for finding the maxima of a point set.