Time complexity analysis of the dominance degree approach for non-dominated sorting

Sumit Mishra; Maxim Buzdalov; Rakesh Senwar

doi:10.1145/3377929.3389900

Time complexity analysis of the dominance degree approach for non-dominated sorting

Sumit Mishra, Maxim Buzdalov, Rakesh Senwar

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

6 Citations (Scopus)

Abstract

Non-dominated sorting is a procedure which is heavily used by many evolutionary multiobjective algorithms. Despite it can be done in polynomial time, it remains an asymptotical bottleneck in many of these algorithms. What is more, some algorithms for non-dominated sorting, which are fast on average, are ridiculously slow in the worst case. Here we prove that a recent algorithm, the dominance degree approach from the paper "Ranking Vectors by Means of the Dominance Degree Matrix" by Zhou et al., has the worst-case time complexity of Θ(M N2 + N3). The Θ(N3) term, which is unusually high for this problem, indicates that this particular algorithm can not be recommended for performance-critical applications.

Original language	English
Title of host publication	GECCO '20
Subtitle of host publication	Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion
Publisher	Association for Computing Machinery
Pages	169-170
Number of pages	2
ISBN (Print)	978-1-4503-7127-8
DOIs	https://doi.org/10.1145/3377929.3389900
Publication status	Published - 08 Jul 2020
Externally published	Yes
Event	GECCO 2020 - Genetic and Evolutionary Computation Conference - Cancun, Mexico Duration: 08 Jul 2020 → 12 Jul 2020

Conference

Conference	GECCO 2020 - Genetic and Evolutionary Computation Conference
Country/Territory	Mexico
City	Cancun
Period	08 Jul 2020 → 12 Jul 2020

Keywords

dominance degree
dominance degree matrix
non-dominated sorting
time complexity

Access to Document

10.1145/3377929.3389900

Permanent link

Persistent link

Cite this

@inproceedings{f20f510fa48547bf9fb9f128cb63d31b,

title = "Time complexity analysis of the dominance degree approach for non-dominated sorting",

abstract = "Non-dominated sorting is a procedure which is heavily used by many evolutionary multiobjective algorithms. Despite it can be done in polynomial time, it remains an asymptotical bottleneck in many of these algorithms. What is more, some algorithms for non-dominated sorting, which are fast on average, are ridiculously slow in the worst case. Here we prove that a recent algorithm, the dominance degree approach from the paper {"}Ranking Vectors by Means of the Dominance Degree Matrix{"} by Zhou et al., has the worst-case time complexity of Θ(M N2 + N3). The Θ(N3) term, which is unusually high for this problem, indicates that this particular algorithm can not be recommended for performance-critical applications.",

keywords = "dominance degree, dominance degree matrix, non-dominated sorting, time complexity",

author = "Sumit Mishra and Maxim Buzdalov and Rakesh Senwar",

year = "2020",

month = jul,

day = "8",

doi = "10.1145/3377929.3389900",

language = "English",

isbn = "978-1-4503-7127-8",

pages = "169--170",

booktitle = "GECCO '20",

publisher = "Association for Computing Machinery",

address = "United States of America",

note = "GECCO 2020 - Genetic and Evolutionary Computation Conference ; Conference date: 08-07-2020 Through 12-07-2020",

}

Mishra, S, Buzdalov, M & Senwar, R 2020, Time complexity analysis of the dominance degree approach for non-dominated sorting. in GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, pp. 169-170, GECCO 2020 - Genetic and Evolutionary Computation Conference, Cancun, Mexico, 08 Jul 2020. https://doi.org/10.1145/3377929.3389900

Time complexity analysis of the dominance degree approach for non-dominated sorting. / Mishra, Sumit; Buzdalov, Maxim; Senwar, Rakesh.
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery, 2020. p. 169-170.

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

TY - GEN

T1 - Time complexity analysis of the dominance degree approach for non-dominated sorting

AU - Mishra, Sumit

AU - Buzdalov, Maxim

AU - Senwar, Rakesh

PY - 2020/7/8

Y1 - 2020/7/8

N2 - Non-dominated sorting is a procedure which is heavily used by many evolutionary multiobjective algorithms. Despite it can be done in polynomial time, it remains an asymptotical bottleneck in many of these algorithms. What is more, some algorithms for non-dominated sorting, which are fast on average, are ridiculously slow in the worst case. Here we prove that a recent algorithm, the dominance degree approach from the paper "Ranking Vectors by Means of the Dominance Degree Matrix" by Zhou et al., has the worst-case time complexity of Θ(M N2 + N3). The Θ(N3) term, which is unusually high for this problem, indicates that this particular algorithm can not be recommended for performance-critical applications.

AB - Non-dominated sorting is a procedure which is heavily used by many evolutionary multiobjective algorithms. Despite it can be done in polynomial time, it remains an asymptotical bottleneck in many of these algorithms. What is more, some algorithms for non-dominated sorting, which are fast on average, are ridiculously slow in the worst case. Here we prove that a recent algorithm, the dominance degree approach from the paper "Ranking Vectors by Means of the Dominance Degree Matrix" by Zhou et al., has the worst-case time complexity of Θ(M N2 + N3). The Θ(N3) term, which is unusually high for this problem, indicates that this particular algorithm can not be recommended for performance-critical applications.

KW - dominance degree

KW - dominance degree matrix

KW - non-dominated sorting

KW - time complexity

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85089745379&origin=resultslist

U2 - 10.1145/3377929.3389900

DO - 10.1145/3377929.3389900

M3 - Conference Proceeding (Non-Journal item)

SN - 978-1-4503-7127-8

SP - 169

EP - 170

BT - GECCO '20

PB - Association for Computing Machinery

T2 - GECCO 2020 - Genetic and Evolutionary Computation Conference

Y2 - 8 July 2020 through 12 July 2020

ER -

Time complexity analysis of the dominance degree approach for non-dominated sorting

Abstract

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this