Filter Sort Is Ω(N3) in the Worst Case

Sumit Mishra, Maxim Buzdalov

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

33 Downloads (Pure)

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 N points and M objectives in time asymptotically smaller than MN2.

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(MN2). 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 Ω(N3). In particular, we present a scenario which requires Filter Sort to perform Θ(N3) 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 languageEnglish
Title of host publicationParallel Problem Solving from Nature – PPSN XVI - 16th International Conference, PPSN 2020, Proceedings
EditorsThomas Bäck, Mike Preuss, André Deutz, Michael Emmerich, Hao Wang, Carola Doerr, Heike Trautmann
PublisherSpringer Nature
Pages675-685
Number of pages11
ISBN (Electronic)978-3-030-58115-2
ISBN (Print)978-3-030-58114-5
DOIs
Publication statusPublished - 02 Sept 2020

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
Volume12270
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 Ω(N3) in the Worst Case'. Together they form a unique fingerprint.

Cite this