## Abstract

Non-dominated sorting is a crucial operation used in many popular evolutionary multiobjective algorithms. The problem of non-dominated sorting, although solvable in polynomial time, is surprisingly difficult, and no algorithm is yet known which solves any instance on

For this reason, many algorithm designers concentrate on reducing the leading constant and on (implicitly) tailoring their algorithms to inputs typical to evolutionary computation. While doing that, they sometimes forget to ensure that the worst-case running time of their algorithm is still

In this paper we prove that a recent algorithm for non-dominated sorting, called Filter Sort, has the worst-case complexity of Ω(

*N*points and*M*objectives in time asymptotically smaller than*MN*^{2}.For this reason, many algorithm designers concentrate on reducing the leading constant and on (implicitly) tailoring their algorithms to inputs typical to evolutionary computation. While doing that, they sometimes forget to ensure that the worst-case running time of their algorithm is still

*O*(*MN*^{2}). This is undesirable, especially if the inputs which make the algorithm work too slow can occur spontaneously. However, even if a counterexample is hard to find, the fact that it exists is still a weak point, as this can be exploited and lead to denial of service and other kinds of misbehaving.In this paper we prove that a recent algorithm for non-dominated sorting, called Filter Sort, has the worst-case complexity of Ω(

*N*^{3}). In particular, we present a scenario which requires Filter Sort to perform Θ(*N*^{3}) dominance comparisons, where each comparison, however, needs only*O*(1) elementary operations. Our scenario contains Θ(*N*) non-domination layers, which is a necessary, but by no means a sufficient condition for being difficult for Filter Sort.Original language | English |
---|---|

Title of host publication | Parallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings |

Editors | Thomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann |

Publisher | Springer Nature |

Pages | 675-685 |

Number of pages | 11 |

ISBN (Electronic) | 978-3-030-58115-2 |

ISBN (Print) | 978-3-030-58114-5 |

DOIs | |

Publication status | Published - 02 Sept 2020 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Nature |

Volume | 12270 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

## Keywords

- Non-dominated sorting
- Filter sort
- Time complexity

## Fingerprint

Dive into the research topics of 'Filter Sort Is Ω(*N*

^{3}) in the Worst Case'. Together they form a unique fingerprint.