Name
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/ITA.2014.6804207 | ITA |
Keywords | Field | DocType |
combinatorial mathematics,optimisation,partial differential equations,sorting,Hamilton-Jacobi partial differential equation,PDE,anomaly detection problem,approximate nondominated sorting algorithm,combinatorial problem,continuum limit,multiobjective optimization,nondominated fronts,Hamilton-Jacobi equations,Non-dominated sorting,Pareto-optimality,antichain partition,longest chain problem,multi-objective optimization,numerical schemes,partial differential equations | Sublinear function,Discrete mathematics,Anomaly detection,Mathematical optimization,Combinatorics,Computer science,Level set,Multi-objective optimization,Sorting,Almost surely,Partial differential equation,Sorting algorithm | Conference |
Citations | PageRank | References |
1 | 0.35 | 16 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeff Calder | 1 | 65 | 11.47 |
| Selim Esedoglu | 2 | 1000 | 49.59 |
| Alfred O. Hero III | 3 | 2600 | 301.12 |