A PDE-Based Approach to Non-Dominated Sorting

  • Selim Esedoglu (University of Michigan at Ann Arbor)
A3 01 (Sophus-Lie room)


Non-dominated sorting is a fundamental problem in multi- objective optimization. We show that non-dominated sorting of a sequence of i.i.d. random variables in Euclidean space has a continuum limit that corresponds to solving a partial differential equation (specifically, a Hamilton-Jacobi equation) involving the probability density function of the random variables. We give an efficient numerical scheme for computing the viscosity solution of this Hamilton-Jacobi equation, and show how it can be used to design a fast algorithm for approximate non-dominated sorting. We demonstrate the advantages of this approach on a large scale real data application of anomaly detection in pedestrian trajectories captured from an overhead camera. Joint work with Jeff Calder and Alfred Hero (Ph.D. thesis work of Jeff Calder).

Katja Heid

MPI for Mathematics in the Sciences Contact via Mail

Upcoming Events of this Seminar