Physical Sciences and Mathematics Commons^™

Combinatorial Problems Related To Optimal Transport And Parking Functions, Jan Kretschmann

Theses and Dissertations

In the first part of this work, we provide contributions to optimal transport through work on the discrete Earth Mover's Distance (EMD).We provide a new formula for the mean EMD by computing three different formulas for the sum of width-one matrices: the first two formulas apply the theory of abstract simplicial complexes and result from a shelling of the order complex, whereas the last formula uses Young tableaux. Subsequently, we employ this result to compute the EMD under different cost matrices satisfying the Monge property. Additionally, we use linear programming to compute the EMD under non-Monge cost matrices, giving an …