Greedy Hypervolume Subset Selection in Low Dimensions.
Given a nondominated point set [Formula: see text] of size [Formula: see text] and a suitable reference point [Formula: see text], the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size [Formula: see text] that maximizes the hypervolume indicator. It arises in connection with multiobjective selection and archiving strategies, as well as Pareto-front approximation postprocessing 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 [Formula: see text]. In contrast, the best upper bound available for [Formula: see text] is [Formula: see text]. Since the hypervolume indicator is a monotone submodular function, the HSSP can be approximated to a factor of [Formula: see text] using a greedy strategy. In this article, greedy [Formula: see text]-time algorithms for the HSSP in 2 and 3 dimensions are proposed, matching the complexity of current exact algorithms for the 2-dimensional case, and considerably improving upon recent complexity results for this approximation problem.
CISUC, Department of Informatics Engineering, University of Coimbra, Pólo II, P-3030 290 Coimbra, Portugal apg@dei.uc.pt.
Andreia P
AP
Guerreiro
CISUC, Department of Informatics Engineering, University of Coimbra, Pólo II, P-3030 290 Coimbra, Portugal cmfonsec@dei.uc.pt.
Carlos M
CM
Fonseca
CISUC, Department of Informatics Engineering, University of Coimbra, Pólo II, P-3030 290 Coimbra, Portugal paquete@dei.uc.pt.
Luís
L
Paquete
D000465:Algorithms; D008962:Models, Theoretical
Hypervolume indicator; greedy algorithm; monotone submodular function; multiobjective optimization; subset selection