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

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

61 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationGECCO 2020 Companion - Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
PublisherACM
Pages185-186
Number of pages2
ISBN (Electronic)9781450371278
DOIs
Publication statusPublished - 8 Jul 2020
MoE publication typeA4 Article in a conference publication
EventGenetic and Evolutionary Computation Conference - Cancun, Mexico
Duration: 8 Jul 202012 Jul 2020

Conference

ConferenceGenetic and Evolutionary Computation Conference
Abbreviated titleGECCO
CountryMexico
CityCancun
Period08/07/202012/07/2020

Fingerprint Dive into the research topics of 'Worst-case conditional hardness and fast algorithms with random inputs for non-dominated sorting'. Together they form a unique fingerprint.

Cite this