## April 28, 2017:

#
Greedy Hypervolume Subset Selection in the Three-Objective Case

##
Pedro Matias

**Abstract:**
Given a non-dominated point set $X \subset \mathbb{R}^d$ of size $n$ and a
suitable reference point $r \in \mathbb{R}^d$, the Hypervolume Subset Selection
Problem (HSSP) consists of finding a subset of size $k \le 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(n^{\frac{d}{2}} \log n + n^{n-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(n(k + \log n))$, which considerably improves upon
recent complexity results for this approximation problem.

Paper by Guerreiro, Fonseca, and Paquete, at GECCO '15, Annual Conference on
Genetic and Evolutionary Computation