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

Maxim Buzdalov, A. A. Shalyto

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

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 languageEnglish
Title of host publicationParallel Problem Solving from Nature -- PPSN XIII
Subtitle of host publication13th International Conference, Ljubljana, Slovenia, September 13-17,2014, Proceedings
EditorsThomas Bartz-Beielstein, Jürgen Branke, Bogdan Filipič, Jim Smith
PublisherSpringer Nature
Pages528-537
Number of pages10
ISBN (Electronic)978-3-319-10762-2, 3319107623
ISBN (Print)978-3-319-10761-5, 3319107615
DOIs
Publication statusPublished - 24 Sept 2014
Externally publishedYes
EventProceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII - Ljubljana, Slovenia
Duration: 13 Sept 201417 Sept 2014

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
Volume8672
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceProceeding 13th International Conference Parallel Problem Solving from Nature -- PPSN XIII
Country/TerritorySlovenia
CityLjubljana
Period13 Sept 201417 Sept 2014

Keywords

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

Fingerprint

Dive into the research topics of 'A Provably Asymptotically Fast Version of the Generalized Jensen Algorithm for Non-dominated Sorting'. Together they form a unique fingerprint.

Cite this