Counterexample to the best-case running time of efficient non-dominated sorting algorithm
Paras Nigam, Sumit Mishra · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2022
Non-dominated sorting is one of the important steps in Pareto dominance-based multiobjective evolutionary algorithms. In this paper, we show that the number of comparisons in the best case of an approach, Efficient Non-dominated Sort (ENS) from the paper "An Efficient Approach to Nondominated Sorting for Evolutionary Multiobjective Optimization" by Zhang et al., is not correct. For this purpose, we have identified a scenario where the approach performs less number of comparisons than that of reported in the paper.