A direct verification argument for the Hamilton–Jacobi equation continuum limit of nondominated sorting. (August 2016) - Calder, Jeff
Abstract: Nondominated sorting is a combinatorial algorithm that sorts points in Euclidean space into layers according to a partial order. It was recently shown that nondominated sorting of random points has a Hamilton–Jacobi equation continuum limit. The original proof, given in Calder et al. (2014), relies on a continuum variational problem. In this paper, we give a new proof using a direct verification argument that completely avoids the variational interpretation. We believe this may be generalized to apply to other stochastic homogenization problems for which there is no obvious underlying variational principle.