Time complexity analysis of the dominance degree approach for non-dominated sorting

Sumit Mishra, Maxim Buzdalov, Rakesh Senwar

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

Abstract

Non-dominated sorting is a procedure which is heavily used by many evolutionary multiobjective algorithms. Despite it can be done in polynomial time, it remains an asymptotical bottleneck in many of these algorithms. What is more, some algorithms for non-dominated sorting, which are fast on average, are ridiculously slow in the worst case. Here we prove that a recent algorithm, the dominance degree approach from the paper "Ranking Vectors by Means of the Dominance Degree Matrix" by Zhou et al., has the worst-case time complexity of Θ(M N2 + N3). The Θ(N3) term, which is unusually high for this problem, indicates that this particular algorithm can not be recommended for performance-critical applications.
Original languageEnglish
Title of host publicationGECCO '20
Subtitle of host publicationProceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
PublisherAssociation for Computing Machinery
Pages169-170
Number of pages2
ISBN (Print)978-1-4503-7127-8
DOIs
Publication statusPublished - 08 Jul 2020
Externally publishedYes
EventGECCO 2020 - Genetic and Evolutionary Computation Conference - Cancun, Mexico
Duration: 08 Jul 202012 Jul 2020

Conference

ConferenceGECCO 2020 - Genetic and Evolutionary Computation Conference
Country/TerritoryMexico
CityCancun
Period08 Jul 202012 Jul 2020

Keywords

  • dominance degree
  • dominance degree matrix
  • non-dominated sorting
  • time complexity

Fingerprint

Dive into the research topics of 'Time complexity analysis of the dominance degree approach for non-dominated sorting'. Together they form a unique fingerprint.

Cite this