Greedy Hypervolume Subset Selection in Low Dimensions

作     者：Guerreiro, Andreia P. Fonseca, Carlos M. Paquete, Luis 

作者机构：Univ Coimbra Dept Informat Engn CISUC Polo 2 P-3030290 Coimbra Portugal 

出 版 物：《EVOLUTIONARY COMPUTATION》 (调优计算)

年 卷 期：2016年第24卷第3期

页      面：521-544页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Portuguese Foundation for Science and Technology (FCT) European Regional Development Fund (FEDER) through COMPETE-Operational Program for Competitiveness and Internationalization (POCI) iCIS project QREN in the scope of the Mais Centro Program [CENTRO-07-ST24-FEDER-002003] FEDER FCT - European Social Fund [SFHR/BD/77725/2011] Portuguese Ministry of Education and Science 

主　　题：Hypervolume indicator multiobjective optimization subset selection monotone submodular function greedy algorithm 

摘      要：Given a nondominated point set X subset of R-d of size n and a suitable reference point r is an element of R-d, the Hypervolume Subset Selection Problem (HSSP) consists of finding a subset of size k 2 is O(n(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. In this article, greedy O(n(k + log n))-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.