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

  • Mar 12, 2024 tba with Theresa Simon
  • Mar 26, 2024 tba with Phan Thành Nam
  • Mar 26, 2024 tba with Dominik Schmid
  • May 7, 2024 tba with Manuel Gnann
  • May 14, 2024 tba with Barbara Verfürth
  • May 14, 2024 tba with Lisa Hartung
  • Jun 25, 2024 tba with Paul Dario
  • Jul 16, 2024 tba with Michael Loss