On the complexity of computing the hypervolume indicator
| dc.contributor.author | Beume, Nicola | de |
| dc.contributor.author | Fonseca, Carlos M. | de |
| dc.contributor.author | López-Ibáñez, Manuel | de |
| dc.contributor.author | Paquete, Luís | de |
| dc.contributor.author | Vahrenhold, Jan | de |
| dc.date.accessioned | 2009-05-12T16:01:32Z | |
| dc.date.available | 2009-05-12T16:01:32Z | |
| dc.date.issued | 2007-12 | de |
| dc.description.abstract | The goal of multi-objective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multi-objective optimizers providing them, unary quality measures are usually applied. Among these, the hypervolume indicator (or S-metric) is of particular relevance due to its good properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for searching the parameter space. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee s Measure Problem. In general, Klee s Measure Problem can be solved in O(n^d/2 log n) for an input instance of size n in d dimensions; as of this writing, it is unknown whether a lower bound higher than Omega(n log n) can be proven. In this article, we derive a lower bound of Omega(n log n) for the complexity of computing the hypervolume indicator in any number of dimensions d > 1 by reducing the problem to the so-called UNIFORMGAP problem. For the three dimensional case, we also present a matching upper bound of O(n log n) that is obtained by extending an algorithm for finding the maxima of a point set. | en |
| dc.identifier.uri | http://hdl.handle.net/2003/26142 | |
| dc.identifier.uri | http://dx.doi.org/10.17877/DE290R-8718 | |
| dc.language.iso | en | de |
| dc.relation.ispartofseries | Reihe CI; 235-07 | de |
| dc.subject | complexity analysis | en |
| dc.subject | computational geometry | en |
| dc.subject | Multi-objective optimization | en |
| dc.subject | performance assessment | en |
| dc.subject.ddc | 004 | de |
| dc.title | On the complexity of computing the hypervolume indicator | en |
| dc.type | Text | de |
| dc.type.publicationtype | report | de |
| dcterms.accessRights | open access |
Files
Original bundle
1 - 1 of 1