A continuum limit for non-dominated sorting

Jeff Calder, Selim Esedoglu, Alfred O. Hero Iii

Abstract

Non-dominated sorting is an important combinatorial problem in multi-objective optimization, which is ubiquitous in many fields of science and engineering. In this paper, we overview the results of some recent work by the authors on a continuum limit for non-dominated sorting. In particular, we have discovered that in the (random) large sample size limit, the non-dominated fronts converge almost surely to the level sets of a function that satisfies a Hamilton-Jacobi partial differential equation (PDE). We show how this PDE can be used to design a fast, potentially sublinear, approximate non-dominated sorting algorithm, and we show the results of applying the algorithm to real data from an anomaly detection problem.
BibTeX
@inproceedings{calder2014continuum,
  author = {Jeff Calder and Selim Esedoglu and Alfred O. Hero III},
  title = {{A continuum limit for non-dominated sorting}},
  booktitle = {ITA},
  year = {2014},
  doi = {10.1109/ita.2014.6804207},
}
Figure