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

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.