Sharath Raghvendra PhotographSharath Raghvendra

Department of Computer Science
Virginia Tech

Email: sharathr at



About Me

I am an Associate Professor in the Department of Computer Science at Virginia Tech. Prior to joining Virginia Tech, I spent two years as a postdoc in the Computer Science and Management Science and Engineering departments at Stanford working with Prof. Leo Guibas and Prof. Ashish Goel. I completed my Ph.D. from the Department of Computer Science at Duke University where I worked with Prof. Pankaj Agarwal. I received my B. Tech (Hons) (Computer Science) from IIIT, Hyderabad.


Research Interests

I’m generally interested in design of efficient algorithms and data structures for problems in computational geometry and graph theory. My research spans problems from geometric optimization, graph theory, computational topology and online algorithms. Check my publications for more information.




Rachita Sowle (Ph. D. candidate, Computer Science)
Kaiyi Zhang (Ph. D. candidate, Computer Science)
Nathaniel Lahn (Ph.D., Computer Science), 2020 (Dissertation work published in SODA '18, SODA '19, SOCG '19, SODA '21)
Krati Nayyar (MS, Computer Science), 2017 (Thesis work published in FOCS '17)
Alexander Daniel Friedman (MS, Mathematics), 2017 (Thesis work published in WAOA '17)
Mariette Wessels (MS, Mathematics), 2017 (Thesis work published in SODA '18)
Mudabir Kabir Asathulla (MS, Computer Engineering), 2017 (Thesis work published in SODA '18)
Harsh Patel (M. Engg., Computer Engineering), 2017
Rutvij Mahajan (MS, Computer Engineering), 2018
Deepika Mulchandani (MS, Computer Science), 2019 (Thesis work published in NeurIPS '19)
Jiacheng Ye (MS, Computer Science), 2020




"The Geometry Behind Logistics Approximation Algorithms for RealTime Delivery" (NSF CRII), $175,000, Feb’15- Jan’18

"Algorithms for Fundamental Optimization Problems in Computational Geometry" (NSF), $450,000, Jul’19- Jun’22



CS4104: Data and Algorithm Analysis (Fall’14, Fall'15, Fall'16, Fall'18)

CS3114: Data Structures and Algorithms (Spring '18, 2 Sections)

CS5114: Theory of Algorithms (Spring '16, Fall '17, Fall '19)

CS6104: Online Algorithms (Spring’15), Geometric Optimization (Spring '17), Combinatorial Algorithms for Network Flow problems (Spring, '19)




A Graph Theoretic Additive Approximation of Optimal Transport
Nathaniel Lahn, Deepika Mulchandani, Sharath Raghvendra
NeurIPS 2019.

A Weighted Approach to Maximum Cardinality Bipartite Matching Problem with Applications in Geometric Settings
Nathaniel Lahn, Sharath Raghvendra
SOCG 2019.

A Faster Algorithm for Minimum-Cost Matching in Minor Free Graphs
Nathaniel Lahn, Sharath Raghvendra
SODA 2019.

Improved Topological Approximations by Digitization
Aruni Choudhary, Michael Kerber, Sharath Raghvendra
SODA 2019.

Optimal Analysis of an Online Algorithm for the Bipartite Matching Problem on a Line
Sharath Raghvendra
SOCG 2018.

A Grid-Based Approximation Algorithm for the Minimum Weight Triangulation Problem
Sharath Raghvendra, Mariette Wessels
SODA 2018.

A Faster Algorithm for Minimum-Cost Bipartite Perfect Matching in Planar Graphs
Mudabir Kabir Asathulla, Sanjeev Khanna, Nathaniel Lahn, Sharath Raghvendra
SODA 2018.

Improved Approximate Rips Filtration with Shifted Integer Lattices
Aruni Choudhary, Michael Kerber, Sharath Raghvendra
ESA 2017.

An Input Sensitive Online Algorithm for the Metric Bipartite Matching Problem
Krati Nayyar, Sharath Raghvendra
FOCS 2017.

A k-Median Based Online Algorithm for the Stochastic k-Server Problem
Abhijin Adiga, Alexander D. Friedman, Sharath Raghvendra
WAOA 2017.

Robust and Optimal Online Algorithm for the Minimum Metric Bipartite Matching
Sharath Raghvendra
APPROX 2016.

Polynomial-Sized Topological Approximations Using the Permutahedron
Aruni Choudhary, Michael Kerber, Sharath Raghvendra
SOCG 2016.

Approximation and Streaming Algorithms for Projective Clustering via Random Projections
Michael Kerber, Sharath Raghvendra
CCCG 2015.

Connectivity in Random Forests and Credit Networks
Ashish Goel, Sanjeev Khanna, Sharath Raghvendra, Hongyang Zhang
SODA 2015.

Approximation Algorithms for Bipartite Matching with Metric and Geometric Costs
Pankaj K. Agarwal, R. Sharathkumar
STOC 2014.

Approximate Cech Complex in Low and High Dimensions
Michael Kerber, R. Sharathkumar
ISAAC 2013.

A Sub-Quadratic Algorithm For Bipartite Matching of Planar Points with Bounded Integer Coordinates
R. Sharathkumar.
SOCG 2013

A Near-Linear Time ε-Approximation Algorithm for Geometric Bipartite Matching
R. Sharathkumar, Pankaj K. Agarwal.
STOC 2012

Algorithms for Transportation Problem in Geometric Settings
R. Sharathkumar, Pankaj K. Agarwal.
SODA 2012

Streaming Algorithms for Extent Problems in High Dimensions
Pankaj K. Agarwal, R. Sharathkumar
SODA 2010 (Appears in Algorithmica)

Approximate Euclidean Shortest-paths amid Convex Obstacles
Pankaj K. Agarwal, R. Sharathkumar, Hai Yu.
SODA 2009

On approximate geodesic-distance queries amid deforming point clouds
Pankaj K. Agarwal, Alon Efrat, R. Sharathkumar, Hai Yu.
WAFR 2008

Range Aggregate Proximity Queries
R. Sharathkumar, Prosenjit Gupta.
Technical Report, 2007.

Range Aggregate Proximity Detection for Design Rule Checking in VLSI layouts
R. Sharathkumar, Prosenjit Gupta.
CCCG, 2006.