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

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion Cynhadledd › Trafodion Cynhadledd (ISBN)

12 Dyfyniadau (Scopus)

Crynodeb

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.

Iaith wreiddiol	Saesneg
Teitl	2015 IEEE Congress on Evolutionary Computation (CEC)
Is-deitl	Proceedings
Cyhoeddwr	IEEE Press
Tudalennau	1853-1860
Nifer y tudalennau	8
ISBN (Electronig)	978-1-4799-7492-4
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1109/CEC.2015.7257112
Statws	Cyhoeddwyd - 14 Medi 2015
Cyhoeddwyd yn allanol	Ie
Digwyddiad	IEEE Congress on Evolutionary Computation, CEC 2015 - Sendai, Siapan Hyd: 25 Mai 2015 → 28 Mai 2015

Cynhadledd

Cynhadledd	IEEE Congress on Evolutionary Computation, CEC 2015
Gwlad/Tiriogaeth	Siapan
Dinas	Sendai
Cyfnod	25 Mai 2015 → 28 Mai 2015

Mynediad at Ddogfen

10.1109/CEC.2015.7257112

Cysylltiad parhaol

Dolen barhaus

Ffeiliau eraill a chysylltiadau

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

Dyfynnu hyn

@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

Crynodeb

Cynhadledd

Mynediad at Ddogfen

Cysylltiad parhaol

Ffeiliau eraill a chysylltiadau

Ôl bys

Dyfynnu hyn