Quarterly (spring, summer, fall, winter)
176 pp. per issue
7 x 10
ISSN
1063-6560
E-ISSN
1530-9304
2014 Impact factor:
2.37

Evolutionary Computation

Fall 2016, Vol. 24, No. 3, Pages 521-544
(doi: 10.1162/EVCO_a_00188)
© 2016 Massachusetts Institute of Technology
Greedy Hypervolume Subset Selection in Low Dimensions
Article PDF (2.19 MB)
Abstract

Given a nondominated point set of size and a suitable reference point , the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size 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 . In contrast, the best upper bound available for is . Since the hypervolume indicator is a monotone submodular function, the HSSP can be approximated to a factor of using a greedy strategy. In this article, greedy -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.