Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting

Sorrachai Yingchareonthawornchai, Proteek Chandan Roy, Bundit Laekhanukit, Eric Torng, Kalyanmoy Deb

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

1 Sitaatiot (Scopus)
123 Lataukset (Pure)


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. We show that the O(mn2) running time is nearly optimal by proving an almost matching conditional lower bound: for any ∈ > 0, and ω(log n) ≤ m ≤ (log n)o(1), there is no O(mn2-ϵ)-time algorithm for NDS or NDS1 unless a popular conjecture in fine-grained complexity theory is false. To complete our results, we present an algorithm for NDS with an expected running time O(mn + n2/m + n log2 n) on uniform random inputs.

OtsikkoGECCO 2020 Companion - Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
ISBN (elektroninen)9781450371278
DOI - pysyväislinkit
TilaJulkaistu - 8 heinäk. 2020
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaGenetic and Evolutionary Computation Conference - Cancun, Meksiko
Kesto: 8 heinäk. 202012 heinäk. 2020


ConferenceGenetic and Evolutionary Computation Conference


Sukella tutkimusaiheisiin 'Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä