## Abstract

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*.

Original language | English |
---|---|

Title of host publication | GECCO 2016 |

Subtitle of host publication | Proceedings of the 2016 Genetic and Evolutionary Computation Conference |

Editors | Tobias Friedrich, Frank Neumann, Andrew M. Sutton |

Publisher | Association for Computing Machinery, Inc |

Pages | 613-620 |

Number of pages | 8 |

ISBN (Electronic) | 9781450342063 |

DOIs | |

Publication status | Published - 20 Jul 2016 |

Externally published | Yes |

Event | 2016 Genetic and Evolutionary Computation Conference, GECCO 2016 - Denver, United States of America Duration: 20 Jul 2016 → 24 Jul 2016 |

### Publication series

Name | GECCO 2016 - Proceedings of the 2016 Genetic and Evolutionary Computation Conference |
---|

### Conference

Conference | 2016 Genetic and Evolutionary Computation Conference, GECCO 2016 |
---|---|

Country/Territory | United States of America |

City | Denver |

Period | 20 Jul 2016 → 24 Jul 2016 |

## Keywords

- Divide-and-conquer
- E-indicator
- Multiobjective optimization
- Orthant search
- Performance evaluation
- Range search