A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting

Maxim Buzdalov; A. A. Shalyto

doi:10.1007/978-3-319-10762-2_52

A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting

Maxim Buzdalov, A. A. Shalyto

ITMO University

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

42 Dyfyniadau (Scopus)

Crynodeb

The non-dominated sorting algorithm by Jensen, generalized by Fortin et al to handle the cases of equal objective values, has the running time complexity of O(N logK − 1 N) in the general case. Here N is the number of points, K is the number of objectives and K is thought to be a constant when N varies. However, the complexity was not proven to be the same in the worst case.

A slightly modified version of the algorithm is presented, for which it is proven that its worst-case running time complexity is O(N logK − 1 N).

Iaith wreiddiol	Saesneg
Teitl	Parallel Problem Solving from Nature -- PPSN XIII
Is-deitl	13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings
Golygyddion	Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, Jim Smith
Cyhoeddwr	Springer Nature
Tudalennau	528-537
Nifer y tudalennau	10
ISBN (Electronig)	978-3-319-10762-2, 3319107623
ISBN (Argraffiad)	978-3-319-10761-5, 3319107615
Dynodwyr Gwrthrych Digidol (DOIs)	https://doi.org/10.1007/978-3-319-10762-2_52
Statws	Cyhoeddwyd - 24 Medi 2014
Cyhoeddwyd yn allanol	Ie
Digwyddiad	Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII - Ljubljana, Slofenia Hyd: 13 Medi 2014 → 17 Medi 2014

Cyfres gyhoeddiadau

Enw	Lecture Notes in Computer Science
Cyhoeddwr	Springer Nature
Cyfrol	8672
ISSN (Argraffiad)	0302-9743
ISSN (Electronig)	1611-3349

Cynhadledd

Cynhadledd	Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII
Gwlad/Tiriogaeth	Slofenia
Dinas	Ljubljana
Cyfnod	13 Medi 2014 → 17 Medi 2014

Mynediad at Ddogfen

10.1007/978-3-319-10762-2_52

Cysylltiad parhaol

Dolen barhaus

Ffeiliau eraill a chysylltiadau

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

Dyfynnu hyn

Buzdalov, M., & Shalyto, A. A. (2014). A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting. Yn T. Bartz-Beielstein, J. Branke, B. Filipič, & J. Smith (Gol.), Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings (tt. 528-537). (Lecture Notes in Computer Science; Cyfrol 8672). Springer Nature. https://doi.org/10.1007/978-3-319-10762-2_52

Buzdalov, Maxim ; Shalyto, A. A. / A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting. Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings. Gol. / Thomas Bartz-Beielstein ; Jürgen Branke ; Bogdan Filipič ; Jim Smith. Springer Nature, 2014. tt. 528-537 (Lecture Notes in Computer Science).

@inproceedings{cac1b4ebbcb24692ba91372cd2c3a3e9,

title = "A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting",

abstract = "The non-dominated sorting algorithm by Jensen, generalized by Fortin et al to handle the cases of equal objective values, has the running time complexity of O(N logK − 1 N) in the general case. Here N is the number of points, K is the number of objectives and K is thought to be a constant when N varies. However, the complexity was not proven to be the same in the worst case. A slightly modified version of the algorithm is presented, for which it is proven that its worst-case running time complexity is O(N logK − 1 N).",

keywords = "non-dominated sorting, worst-case running time complexity, multi-objective optimization",

author = "Maxim Buzdalov and Shalyto, \{A. A.\}",

year = "2014",

month = sep,

day = "24",

doi = "10.1007/978-3-319-10762-2\_52",

language = "English",

isbn = "978-3-319-10761-5",

series = "Lecture Notes in Computer Science",

publisher = "Springer Nature",

pages = "528--537",

editor = "Thomas Bartz-Beielstein and J{\"u}rgen Branke and Bogdan Filipi{\v c} and Jim Smith",

booktitle = "Parallel Problem Solving from Nature -- PPSN XIII",

address = "Switzerland",

note = "Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII ; Conference date: 13-09-2014 Through 17-09-2014",

}

Buzdalov, M & Shalyto, AA 2014, A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting. yn T Bartz-Beielstein, J Branke, B Filipič & J Smith (gol.), Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings. Lecture Notes in Computer Science, cyfrol. 8672, Springer Nature, tt. 528-537, Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII, Ljubljana, Slofenia, 13 Medi 2014. https://doi.org/10.1007/978-3-319-10762-2_52

A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting. / Buzdalov, Maxim; Shalyto, A. A.
Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings. gol. / Thomas Bartz-Beielstein; Jürgen Branke; Bogdan Filipič; Jim Smith. Springer Nature, 2014. t. 528-537 (Lecture Notes in Computer Science; Cyfrol 8672).

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

TY - GEN

T1 - A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting

AU - Buzdalov, Maxim

AU - Shalyto, A. A.

PY - 2014/9/24

Y1 - 2014/9/24

N2 - The non-dominated sorting algorithm by Jensen, generalized by Fortin et al to handle the cases of equal objective values, has the running time complexity of O(N logK − 1 N) in the general case. Here N is the number of points, K is the number of objectives and K is thought to be a constant when N varies. However, the complexity was not proven to be the same in the worst case. A slightly modified version of the algorithm is presented, for which it is proven that its worst-case running time complexity is O(N logK − 1 N).

AB - The non-dominated sorting algorithm by Jensen, generalized by Fortin et al to handle the cases of equal objective values, has the running time complexity of O(N logK − 1 N) in the general case. Here N is the number of points, K is the number of objectives and K is thought to be a constant when N varies. However, the complexity was not proven to be the same in the worst case. A slightly modified version of the algorithm is presented, for which it is proven that its worst-case running time complexity is O(N logK − 1 N).

KW - non-dominated sorting

KW - worst-case running time complexity

KW - multi-objective optimization

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

U2 - 10.1007/978-3-319-10762-2_52

DO - 10.1007/978-3-319-10762-2_52

M3 - Conference Proceeding (ISBN)

SN - 978-3-319-10761-5

SN - 3319107615

T3 - Lecture Notes in Computer Science

SP - 528

EP - 537

BT - Parallel Problem Solving from Nature -- PPSN XIII

A2 - Bartz-Beielstein, Thomas

A2 - Branke, Jürgen

A2 - Filipič, Bogdan

A2 - Smith, Jim

PB - Springer Nature

T2 - Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII

Y2 - 13 September 2014 through 17 September 2014

ER -

Buzdalov M, Shalyto AA. A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting. Yn Bartz-Beielstein T, Branke J, Filipič B, Smith J, golygyddion, Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings. Springer Nature. 2014. t. 528-537. (Lecture Notes in Computer Science). Epub 2014 Medi 11. doi: 10.1007/978-3-319-10762-2_52

A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting

Crynodeb

Cyfres gyhoeddiadau

Cynhadledd

Mynediad at Ddogfen

Cysylltiad parhaol

Ffeiliau eraill a chysylltiadau

Ôl bys

Dyfynnu hyn