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