## Abstract

Non-dominated sorting is a common routine used in many evolutionary multiobjective algorithms to rank solutions based on the Pareto-dominance relation. Unlike many other problems appearing in evolutionary computation, this problem has a simple formal definition, a number of quite efficient algorithms to solve it, and is relatively well understood.

Unfortunately, a number of recent papers that propose new, and supposedly efficient, algorithms for non-dominated sorting, feature inaccurate analysis, leading to overly optimistic claims. In this paper we prove that a recent algorithm, called Labeling-Oriented Non-Dominated Sorting, or LONSA, has the worst-case running time of Θ(MN3), where N is the number of points and M is the number of objectives, which is much greater than the quadratic upper bound the authors claim. Our proof holds for all M ≥ 4 and essentially reduces LONSA to another algorithm, Deductive Sort, for which the hard test has been constructed before.

Unfortunately, a number of recent papers that propose new, and supposedly efficient, algorithms for non-dominated sorting, feature inaccurate analysis, leading to overly optimistic claims. In this paper we prove that a recent algorithm, called Labeling-Oriented Non-Dominated Sorting, or LONSA, has the worst-case running time of Θ(MN3), where N is the number of points and M is the number of objectives, which is much greater than the quadratic upper bound the authors claim. Our proof holds for all M ≥ 4 and essentially reduces LONSA to another algorithm, Deductive Sort, for which the hard test has been constructed before.

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

Title of host publication | GECCO '21 |

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

Editors | Francisco Chicano |

Publisher | Association for Computing Machinery |

Pages | 189-190 |

Number of pages | 2 |

ISBN (Print) | 9781450383516, 1450383513 |

DOIs | |

Publication status | Published - 08 Jul 2021 |

Externally published | Yes |

Event | GECCO 2021 -Genetic and Evolutionary Computation Conference - Lille, France Duration: 10 Jul 2021 → 14 Jul 2021 |

### Conference

Conference | GECCO 2021 -Genetic and Evolutionary Computation Conference |
---|---|

Country/Territory | France |

City | Lille |

Period | 10 Jul 2021 → 14 Jul 2021 |

## Keywords

- dominance comparisons
- non-dominated sorting
- time complexity