Greedy Hypervolume Subset Selection in the Three-Objective Case
Andreia P. Guerreiro, Carlos M. Fonseca, Luís Paquete · 2015
Given a non-dominated point set X ⊂ Rd of size n and a suitable reference point r ∈ Rd, the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size k > n that maximizes the hypervolume indicator. It arises in connection with multiobjective selection and archiving strategies, as well as Pareto-front approximation post-processing for visualization and/or interaction with a decision maker. Efficient algorithms to solve the HSSP are available only for the 2-dimensional case, achieving a time complexity of O(n(k+log n)). In contrast, the best upper bound available for d>2 is O(nd/2 log n + nn-k). Since the hypervolume indicator is a monotone submodular function, the HSSP can be approximated to a factor of (1-1/e) using a greedy strategy. Such a greedy algorithm for the 3-dimensional HSSP is proposed in this paper. The time complexity of the algorithm is shown to be O(n2), which considerably improves upon recent complexity results for this approximation problem.