8 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…
Improved Topological Approximations by Digitization
Aruni Choudhary, Michael Kerber, Sharath Raghvendra
Čech complexes are useful simplicial complexes for computing and analyzing topological features of data that lies in Euclidean space. Unfortunately, computing these complexes becom…
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…
Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line
Sharath Raghvendra
In the online metric bipartite matching problem, we are given a set of server locations in a metric space. Requests arrive one at a time, and on its arrival, we need to immedia…