## Crynodeb

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.Iaith wreiddiol | Saesneg |
---|---|

Teitl | Parallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings |

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

Cyhoeddwr | Springer Nature |

Tudalennau | 675-685 |

Nifer y tudalennau | 11 |

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

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

Dynodwyr Gwrthrych Digidol (DOIs) | |

Statws | Cyhoeddwyd - 02 Medi 2020 |

### Cyfres gyhoeddiadau

Enw | Lecture Notes in Computer Science |
---|---|

Cyhoeddwr | Springer Nature |

Cyfrol | 12270 |

ISSN (Argraffiad) | 0302-9743 |

ISSN (Electronig) | 1611-3349 |

## Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Filter Sort Is Ω(*N*

^{3}) in the Worst Case'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.