Incremental non-dominated sorting with O(N) insertion for the two-dimensional case

Ilya Yakupov; Maxim Buzdalov

doi:10.1109/CEC.2015.7257112

Incremental non-dominated sorting with O(N) insertion for the two-dimensional case

Ilya Yakupov, Maxim Buzdalov

ITMO University

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (ISBN)

12 Citations (Scopus)

Abstract

We propose a new algorithm for incremental nondominated 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.

Original language	English
Title of host publication	2015 IEEE Congress on Evolutionary Computation (CEC)
Subtitle of host publication	Proceedings
Publisher	IEEE Press
Pages	1853-1860
Number of pages	8
ISBN (Electronic)	978-1-4799-7492-4
DOIs	https://doi.org/10.1109/CEC.2015.7257112
Publication status	Published - 14 Sept 2015
Externally published	Yes
Event	IEEE Congress on Evolutionary Computation, CEC 2015 - Sendai, Japan Duration: 25 May 2015 → 28 May 2015

Conference

Conference	IEEE Congress on Evolutionary Computation, CEC 2015
Country/Territory	Japan
City	Sendai
Period	25 May 2015 → 28 May 2015

Access to Document

10.1109/CEC.2015.7257112

Permanent link

Persistent link

Cite this

@inproceedings{e2437000c8334ec88bf735cb08610dc7,

title = "Incremental non-dominated sorting with O(N) insertion for the two-dimensional case",

abstract = "We propose a new algorithm for incremental nondominated 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.",

author = "Ilya Yakupov and Maxim Buzdalov",

year = "2015",

month = sep,

day = "14",

doi = "10.1109/CEC.2015.7257112",

language = "English",

pages = "1853--1860",

booktitle = "2015 IEEE Congress on Evolutionary Computation (CEC)",

publisher = "IEEE Press",

address = "United States of America",

note = "IEEE Congress on Evolutionary Computation, CEC 2015 ; Conference date: 25-05-2015 Through 28-05-2015",

}

TY - GEN

T1 - Incremental non-dominated sorting with O(N) insertion for the two-dimensional case

AU - Yakupov, Ilya

AU - Buzdalov, Maxim

PY - 2015/9/14

Y1 - 2015/9/14

N2 - We propose a new algorithm for incremental nondominated 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.

AB - We propose a new algorithm for incremental nondominated 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.

UR - https://www.scopus.com/pages/publications/84963575914

U2 - 10.1109/CEC.2015.7257112

DO - 10.1109/CEC.2015.7257112

M3 - Conference Proceeding (ISBN)

SP - 1853

EP - 1860

BT - 2015 IEEE Congress on Evolutionary Computation (CEC)

PB - IEEE Press

T2 - IEEE Congress on Evolutionary Computation, CEC 2015

Y2 - 25 May 2015 through 28 May 2015

ER -

Incremental non-dominated sorting with O(N) insertion for the two-dimensional case

Abstract

Conference

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this