R.Sharathkumar
Department of Computer Science
Stanford University
Email: sharathk at stanford.edu
About Me
I am a post-doctoral scholar in the Geometric Computation Group at Stanford. I completed my Ph.D. from the Department of Computer Science at Duke University. At Duke, I worked with Prof. Pankaj Agarwal. I received my B. Tech (Hons) (Computer Science) from IIIT, Hyderabad.
Research Interests
I am interested in designing approximation and exact algorithms for optimization problems. I enjoy working on fundamental optimization problems such as Minimum Bipartite Matching, TSP, etc.
I am also interested in design of approximation algorithms that solve optimization problems over large scale inputs. In my Ph.D. thesis titled Geometric Approximation Algorithms - A Summary Based Approach , I designed efficient approximation algorithms for fundamental geometric optimization problems using a summary based approach, i.e., quickly compute a compact representation (or summary) of the input and extract an approximately optimal solution from this summary by a relatively slower algorithm. My dissertation won the Duke Computer Science Outstanding Ph.D. dissertation for 2012.
Here is an incomplete list of open questions that I am interested in.
Publications
A Sub-Quadratic Time 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 (To Appear 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.