Projects per year
Abstract
We study the computational complexity of the nondominated sorting problem (NDS): Given a set P of n points in R^{m}, 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 nondominated points in P. NDS has emerged as a critical component for multiobjective optimization problems (MOPs). For m ≤ 3, Θ(n log n)time is known. For a fixed small m > 3, the best bound is O(n log^{m2} n log log n). For larger m, the best result is an O(mn^{2})time algorithm. We show that the O(mn^{2}) 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(mn^{2ϵ})time algorithm for NDS or NDS1 unless a popular conjecture in finegrained complexity theory is false. To complete our results, we present an algorithm for NDS with an expected running time O(mn + n^{2}/m + n log^{2} n) on uniform random inputs.
Original language  English 

Title of host publication  GECCO 2020 Companion  Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion 
Publisher  ACM 
Pages  185186 
Number of pages  2 
ISBN (Electronic)  9781450371278 
DOIs  
Publication status  Published  8 Jul 2020 
MoE publication type  A4 Article in a conference publication 
Event  Genetic and Evolutionary Computation Conference  Cancun, Mexico Duration: 8 Jul 2020 → 12 Jul 2020 
Conference
Conference  Genetic and Evolutionary Computation Conference 

Abbreviated title  GECCO 
Country/Territory  Mexico 
City  Cancun 
Period  08/07/2020 → 12/07/2020 
Fingerprint
Dive into the research topics of 'Worstcase conditional hardness and fast algorithms with random inputs for nondominated sorting'. Together they form a unique fingerprint.Projects
 1 Active

ALGOCom: Novel Algorithmic Techniques through the Lens of Combinatorics
Chalermsook, P., Jindal, G., Franck, M., Spoerhase, J., Jiamjitrak, W., Khodamoradi, K., Yingchareonthawornchai, S., Gadekar, A. & Orgo, L.
01/02/2018 → 31/01/2024
Project: EU: ERC grants