DocumentCode
2222637
Title
Incremental non-dominated sorting with O(N) insertion for the two-dimensional case
Author
Yakupov, Ilya ; Buzdalov, Maxim
Author_Institution
ITMO University, 49 Kronverkskiy av., Saint-Petersburg, Russia, 197101
fYear
2015
fDate
25-28 May 2015
Firstpage
1853
Lastpage
1860
Abstract
We propose a new algorithm for incremental non-dominated sorting of two-dimensional points. The data structure which stores non-dominating layers is based on a tree of Cartesian trees. If there are N points in M layers, the running time for of an insertion is O(M(1 + log(N/M)) + log M log(N/ log M)), which is O(N) in the worst case. This algorithm can be a basic building block for efficient implementations of steady-state multiobjective algorithms such as NSGA-II.
Keywords
Algorithm design and analysis; Complexity theory; Containers; Data structures; Estimation; Sorting; Vegetation;
fLanguage
English
Publisher
ieee
Conference_Titel
Evolutionary Computation (CEC), 2015 IEEE Congress on
Conference_Location
Sendai, Japan
Type
conf
DOI
10.1109/CEC.2015.7257112
Filename
7257112
Link To Document