A faster algorithm for the binary epsilon indicator based on orthant minimum search

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.

We present an efficient algorithm to compute the value of the binary ε-indicator. It reduces the problem to a series of orthant minimum searches, which are solved by an appropriate algorithm. For the latter, we consider two implementations: the one based on a dynamic tree data structure, and the one based on the divide-and-conquer technique. In both cases, evaluation of the binary ε-indicator takes O((n+m)k(log(n+m))max(1, k-2)) time. Empirical evaluation shows that the second implementation has a better performance than the first one, and both of them outperform the naive algorithm for large enough values of n.