{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T15:25:46Z","timestamp":1775143546212,"version":"3.50.1"},"reference-count":22,"publisher":"MIT Press - Journals","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Evolutionary Computation"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1162\/evco_a_00188","type":"journal-article","created":{"date-parts":[[2016,6,15]],"date-time":"2016-06-15T18:09:46Z","timestamp":1466014186000},"page":"521-544","source":"Crossref","is-referenced-by-count":54,"title":["Greedy Hypervolume Subset Selection in Low Dimensions"],"prefix":"10.1162","volume":"24","author":[{"given":"Andreia P.","family":"Guerreiro","sequence":"first","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, P-3030 290 Coimbra, Portugal"}]},{"given":"Carlos M.","family":"Fonseca","sequence":"additional","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, P-3030 290 Coimbra, Portugal"}]},{"given":"Lu\u00eds","family":"Paquete","sequence":"additional","affiliation":[{"name":"CISUC, Department of Informatics Engineering, University of Coimbra, P\u00f3lo II, P-3030 290 Coimbra, Portugal"}]}],"member":"281","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1145\/1527125.1527138"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00009"},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2009.2015575"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2006.08.008"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2007.4424881"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00012"},{"key":"B7","first-page":"589","author":"Bringmann K.","year":"2014","journal-title":"Conference on Genetic and Evolutionary Computation"},{"key":"B8","first-page":"1198","author":"Bringmann K.","year":"2011","journal-title":"Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence\u2014Vol. Two"},{"key":"B9","first-page":"410","author":"Chan T. M","year":"2013","journal-title":"IEEE Symposium on Foundations of Computer Science (FOCS)"},{"key":"B10","volume-title":"Multi-objective optimization using evolutionary algorithms","author":"Deb K","year":"2001"},{"key":"B11","volume-title":"Multicriteria optimization","author":"Ehrgott M.","year":"2005","edition":"2"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19893-9_9"},{"key":"B13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-10762-2_91"},{"key":"B14","first-page":"77","author":"Guerreiro A. P.","year":"2012","journal-title":"Canadian Conference on Computational Geometry (CCCG) 2012"},{"key":"B15","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/2739480.2754812","author":"Guerreiro A. P.","year":"2015","journal-title":"Conference on Genetic and Evolutionary Computation"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-01128-8_11"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2003.1299401"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00157"},{"key":"B19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34413-8_17"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2010.2077298"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0056872"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mitpressjournals.org\/doi\/pdf\/10.1162\/EVCO_a_00188","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T19:40:07Z","timestamp":1656704407000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/24\/3\/521-544\/1028"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1162\/EVCO_a_00188"],"URL":"https:\/\/doi.org\/10.1162\/evco_a_00188","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"value":"1063-6560","type":"print"},{"value":"1530-9304","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,9]]}}}