Labeling-oriented non-dominated sorting is Θ(MN3)

Sumit Mishra, Ved Prakash, Maxim Buzdalov

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


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.
Original languageEnglish
Title of host publicationGECCO '21
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference Companion
EditorsFrancisco Chicano
PublisherAssociation for Computing Machinery, Inc
Number of pages2
ISBN (Print)9781450383516, 1450383513
Publication statusPublished - 08 Jul 2021
Externally publishedYes
EventGECCO 2021 -Genetic and Evolutionary Computation Conference - Lille, France
Duration: 10 Jul 202114 Jul 2021


ConferenceGECCO 2021 -Genetic and Evolutionary Computation Conference
Period10 Jul 202114 Jul 2021


  • dominance comparisons
  • non-dominated sorting
  • time complexity


Dive into the research topics of 'Labeling-oriented non-dominated sorting is Θ(MN3)'. Together they form a unique fingerprint.

Cite this