## 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