12 citations · 12 across the 4 of their papers we have counts for
5 papers
A Push-Relabel Based Additive Approximation for Optimal Transport
Nathaniel Lahn, Sharath Raghvendra, Kaiyi Zhang
Optimal Transport is a popular distance metric for measuring similarity between distributions. Exact algorithms for computing Optimal Transport can be slow, which has motivated the…
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…