A Faster Algorithm for the Binary Epsilon Indicator Based on Orthant Minimum Search
Andrey Vasin, Maxim Buzdalov · 2016
The binary ε-indicator is often used to assess the quality of solutions in multiobjective optimization, and to perform optimization as well. It is normally evaluated using a straightforward θ(nmk) algorithm, where n and m are the number of solutions in the arguments, and k is the number of objectives. This is considered to be fast compared to, for example, the hypervolume indicator, which is #P-hard. However, there are efficient algorithms for the latter, especially for small values of k, while the ε-indicator evaluation is too slow already for n,m > 104 and for any k.