research
∙
04/08/2022
Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching
Given point sets A and B in ℝ^d where A and B have equal size n for some...
share
research
∙
03/07/2022
A Push-Relabel Based Additive Approximation for Optimal Transport
Optimal Transport is a popular distance metric for measuring similarity ...
research
∙
05/11/2021
Improved Approximate Rips Filtrations with Shifted Integer Lattices and Cubical Complexes
Rips complexes are important structures for analyzing topological featur...
research
∙
07/15/2020
An Õ(n^5/4) Time ε-Approximation Algorithm for RMS Matching in a Plane
The 2-Wasserstein distance (or RMS distance) is a useful measure of simi...
research
∙
05/28/2019
A Graph Theoretic Additive Approximation of Optimal Transport
Transportation cost is an attractive similarity measure between probabil...
research
∙
03/25/2019
A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
We present a weighted approach to compute a maximum cardinality matching...
research
∙
12/12/2018
Improved Topological Approximations by Digitization
Čech complexes are useful simplicial complexes for computing and analyzi...
research
∙
07/12/2018
A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs
We give an Õ(n^7/5 (nC))-time algorithm to compute a minimum-cost maximu...
research
∙
03/20/2018
Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line
In the online metric bipartite matching problem, we are given a set S of...
research
∙
06/22/2017
Improved Approximate Rips Filtrations with Shifted Integer Lattices
Rips complexes are important structures for analyzing topological featur...
research
∙
06/10/2017