Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting
Sorrachai Yingchareonthawornchai, Proteek Chandan Roy, Bundit Laekhanukit, Eric K. Torng, Kalyanmoy Deb · 2020
We study the computational complexity of the non-dominated sorting problem (NDS): Given a set P of n points in Rm, for each point p ∈ P, compute ℓ, the length of longest domination chain p1 > p2 > ··· > pℓ = p, where x dominates y (denoted as x > y) if x is not larger than y in every coordinate. A special case of NDS, which we label as NDS1, is to find all the non-dominated points in P. NDS has emerged as a critical component for multi-objective optimization problems (MOPs). For m ≤ 3, Θ(n log n)-time is known. For a fixed small m > 3, the best bound is O(n logm-2 n log log n). For larger m, the best result is an O(mn2)-time algorithm.