Speaker: Jeff Calder (UC Berkeley)

Title: A PDE-proof of the continuum limit of non-dominated sorting

Abstract: Non-dominated sorting is a combinatorial problem that is fundamental in multi-objective optimization, which is ubiquitous in engineering and scientific contexts. The sorting can be viewed as arranging points in Euclidean space into layers according to a partial order. It is equivalent to several well-known problems in probability and combinatorics, including the longest chain problem, and polynuclear growth. Recently, we showed that non-dominated sorting of random points has a continuum limit that corresponds to solving a Hamilton-Jacobi equation in the viscosity sense. Our original proof was based on a continuum variational problem, for which the PDE is the associated Hamilton-Jacobi-Bellman equation. In this talk, I will sketch a new proof that avoids this variational interpretation, and uses only PDE techniques. The proof borrows ideas from the Barles-Souganidis framework for proving convergence of numerical schemes to viscosity solutions. As a result, it seems this proof is more robust, and we believe it can be applied to many other problems that do not have obvious underlying variational principles. I will finish the talk by briefly sketching some current problems of interest.