Sharath Raghvendra

Pouyan Shirzadian

Rachita Sowle

Proceedings of the 41st International Symposium on Computational Geometry, 2025

2024

Fast and Accurate Approximations of the Optimal Transport in Semi-Discrete and Discrete Settings.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

A Combinatorial Algorithm for the Semi-Discrete Optimal Transport Problem.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024

A New Robust Partial p-Wasserstein-Based Metric for Comparing Distributions.

[BibT_eX]

[DOI]

Pouyan Shirzadian

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

A Combinatorial Algorithm for Approximating the Optimal Transport in the Parallel and MPC Settings.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

A Robust Exact Algorithm for the Euclidean Bipartite Matching Problem.

[BibT_eX]

[DOI]

Akshaykumar Gattani

Pouyan Shirzadian

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Computing all Optimal Partial Transports.

[BibT_eX]

[DOI]

Abhijeet Phatak

Chittaranjan Tripathy

Proceedings of the Eleventh International Conference on Learning Representations, 2023

A Higher Precision Algorithm for Computing the $1$-Wasserstein Distance.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

2022

Deterministic, Near-Linear ε-Approximation Algorithm for Geometric Bipartite Matching.

[BibT_eX]

[DOI]

CoRR, 2022

A Push-Relabel Based Additive Approximation for Optimal Transport.

[BibT_eX]

[DOI]

CoRR, 2022

A Scalable Work Function Algorithm for the k-Server Problem.

[BibT_eX]

[DOI]

Rachita Sowle

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

An Improved ε-Approximation Algorithm for Geometric Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the 18th Scandinavian Symposium and Workshops on Algorithm Theory, 2022

Deterministic, near-linear ε-approximation algorithm for geometric bipartite matching.

[BibT_eX]

[DOI]

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Improved approximate rips filtrations with shifted integer lattices and cubical complexes.

[BibT_eX]

[DOI]

J. Appl. Comput. Topol., 2021

An O(n5/4) Time ∊-Approximation Algorithm for RMS Matching in a Plane.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

A Faster Maximum Cardinality Matching Algorithm with Applications in Machine Learning.

[BibT_eX]

[DOI]

Jiacheng Ye

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

2020

An Õ(n5/4) Time ε-Approximation Algorithm for RMS Matching in a Plane.

[BibT_eX]

[DOI]

CoRR, 2020

2019

A Faster Algorithm for Minimum-Cost Bipartite Matching in Minor-Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Improved Topological Approximations by Digitization.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

A Graph Theoretic Additive Approximation of Optimal Transport.

[BibT_eX]

[DOI]

Deepika Mulchandani

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

A Weighted Approach to the Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

2018

A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem.

[BibT_eX]

[DOI]

Mariëtte C. Wessels

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs.

[BibT_eX]

[DOI]

Mudabir Kabir Asathulla

Sanjeev Khanna

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line.

[BibT_eX]

[DOI]

Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017

A k-Median Based Online Algorithm for the Stochastic k-Server Problem.

[BibT_eX]

[DOI]

Abhijin Adiga

Alexander D. Friedman

Proceedings of the Approximation and Online Algorithms - 15th International Workshop, 2017

An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem.

[BibT_eX]

[DOI]

Krati Nayyar

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

Improved Approximate Rips Filtrations with Shifted Integer Lattices.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016

Polynomial-Sized Topological Approximations Using the Permutahedron.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

A Robust and Optimal Online Algorithm for Minimum Metric Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Connectivity in Random Forests and Credit Networks.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Approximation and Streaming Algorithms for Projective Clustering via Random Projections.

[BibT_eX]

[DOI]

Proceedings of the 27th Canadian Conference on Computational Geometry, 2015

2014

Accurate Streaming Support Vector Machines.

[BibT_eX]

[DOI]

Vikram Nathan

CoRR, 2014

Approximation algorithms for bipartite matching with metric and geometric costs.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

2013

Approximate Cech Complexes in Low and High Dimensions.

[BibT_eX]

[DOI]

CoRR, 2013

Approximate Čech Complex in Low and High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Computational Geometry 2013, 2013

2012

Geometric Approximation Algorithms - A Summary Based Approach.

[BibT_eX]

[DOI]

Sharathkumar Raghvendra

PhD thesis, 2012

A near-linear time ε-approximation algorithm for geometric bipartite matching.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Algorithms for the transportation problem in geometric settings.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2010

Streaming Algorithms for Extent Problems in High Dimensions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

Approximate Euclidean shortest paths amid convex obstacles.

[BibT_eX]

[DOI]

Hai Yu

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

On Approximate Geodesic-Distance Queries amid Deforming Point Clouds.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Foundation of Robotics VIII, 2008

2006

Range-Aggregate Proximity Detection for Design Rule Checking in VLSI Layouts.

[BibT_eX]

[DOI]