**Sharath Raghvendra**

Department of Computer
Science

Virginia Tech

Email: sharathr at vt.edu

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.

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 Real‐Time 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.