The binary epsilon-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 Theta(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 epsilon-indicator evaluation is too slow already for n, m > 10(4) and for any k.
We present an efficient algorithm to compute the value of the binary epsilon-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 it dynamic tree data structure, and the one based on the divide-and-conquer technique. In both cases, evaluation of the binary epsilon-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 it.