Hamilton-Jacobi Equations for Sorting and Percolation Problems.

Abstract

In this dissertation we prove continuum limits for some sorting and percolation problems that are important in mathematical, scientific, and engineering contexts. The first problem we study is non-dominated sorting, which is a fundamental combinatorial problem in multi-objective optimization. The sorting can be viewed as arranging points in Euclidean space into fronts according to a partial order. We show that these fronts converge almost surely to the level sets of a function that satisfies a Hamilton-Jacobi equation in the viscosity sense. Of course, multi-objective optimization is ubiquitous in scientific and engineering contexts, and, as it turns out, non-dominated sorting is also equivalent to the longest chain problem, which has a long history in probability and combinatorics. We present a fast numerical scheme for solving this Hamilton-Jacobi equation and prove convergence and various properties of the scheme. We then show how to use the scheme to design a fast approximate non-dominated sorting algorithm and we demonstrate the algorithm on synthetic data as well as a large-scale real-world dataset.

The second problem we study is directed last passage percolation (DLPP), which is a stochastic growth model with applications in directed polymer growth, queuing systems, and stochastic particle systems. DLPP is closely related to the longest chain problem, and by using similar techniques we prove that a DLPP model with macroscopic and discontinuous weights has a continuum limit that corresponds to solving a Hamilton-Jacobi equation. We further prove convergence of a numerical scheme for this Hamilton-Jacobi equation and present an algorithm based on dynamic programming for finding the asymptotic shapes of maximal directed paths.