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

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

40 Citations (Scopus)

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).

Original language	English
Title of host publication	Parallel Problem Solving from Nature -- PPSN XIII
Subtitle of host publication	13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings
Editors	Thomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, Jim Smith
Publisher	Springer Nature
Pages	528-537
Number of pages	10
ISBN (Electronic)	978-3-319-10762-2, 3319107623
ISBN (Print)	978-3-319-10761-5, 3319107615
DOIs	https://doi.org/10.1007/978-3-319-10762-2_52
Publication status	Published - 24 Sept 2014
Externally published	Yes
Event	Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII - Ljubljana, Slovenia Duration: 13 Sept 2014 → 17 Sept 2014

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Nature
Volume	8672
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII
Country/Territory	Slovenia
City	Ljubljana
Period	13 Sept 2014 → 17 Sept 2014

Keywords

non-dominated sorting
worst-case running time complexity
multi-objective optimization

Access to Document

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

Permanent link

Persistent link

Cite this

Buzdalov, M., & Shalyto, A. A. (2014). A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting. In T. Bartz-Beielstein, J. Branke, B. Filipič, & J. Smith (Eds.), Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings (pp. 528-537). (Lecture Notes in Computer Science; Vol. 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. editor / Thomas Bartz-Beielstein ; Jürgen Branke ; Bogdan Filipič ; Jim Smith. Springer Nature, 2014. pp. 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. in T Bartz-Beielstein, J Branke, B Filipič & J Smith (eds), Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings. Lecture Notes in Computer Science, vol. 8672, Springer Nature, pp. 528-537, Proceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII, Ljubljana, Slovenia, 13 Sept 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. ed. / Thomas Bartz-Beielstein; Jürgen Branke; Bogdan Filipič; Jim Smith. Springer Nature, 2014. p. 528-537 (Lecture Notes in Computer Science; Vol. 8672).

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

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/record/display.uri?eid=2-s2.0-84921635994&origin=resultslist

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

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

M3 - Conference Proceeding (Non-Journal item)

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. In Bartz-Beielstein T, Branke J, Filipič B, Smith J, editors, Parallel Problem Solving from Nature -- PPSN XIII: 13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings. Springer Nature. 2014. p. 528-537. (Lecture Notes in Computer Science). Epub 2014 Sept 11. doi: 10.1007/978-3-319-10762-2_52

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

Abstract

Publication series

Conference

Keywords

Access to Document

Permanent link

Other files and links

Fingerprint

Cite this