4 papers
An Time -Approximation Algorithm for RMS Matching in a Plane
Nathaniel Lahn, Sharath Raghvendra
The 2-Wasserstein distance (or RMS distance) is a useful measure of similarity between probability distributions that has exciting applications in machine learning. For discrete di…
A Graph Theoretic Additive Approximation of Optimal Transport
Nathaniel Lahn, Deepika Mulchandani, Sharath Raghvendra
Transportation cost is an attractive similarity measure between probability distributions due to its many useful theoretical properties. However, solving optimal transport exactly…
A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
Nathaniel Lahn, Sharath Raghvendra
We present a weighted approach to compute a maximum cardinality matching in an arbitrary bipartite graph. Our main result is a new algorithm that takes as input a weighted bipartit…
A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
Nathaniel Lahn, Sharath Raghvendra
We give an -time algorithm to compute a minimum-cost maximum cardinality matching (optimal matching) in -minor free graphs with and inte…