
103A, Computer Science Department
35 Olden St
Princeton, NJ 08540
Email: ravishan (at) cs (dot) cmu (dot) edu

About
For Fall 2014, I am a postdoc at the IEOR department in Columbia University, and starting Spring 2015, will be a Researcher at Microsoft Research, India. Prior to this, I was a Simons Postdoctoral Fellow at the Computer Science Department, Princeton University. In 2012, I completed my PhD at CMU where I was fortunate to have Anupam Gupta as my advisor. Long ago, I was an undergrad at IIT Madras. 
Research
My research interests are in approximation algorithms, especially for graphtheoretic problems and sequencing problems. I am also interested in models which incorporate uncertainty in the input such as online algorithms and stochastic optimization. My PhD thesis on Approximation Techniques for Stochastic Combinatorial Optimization can be found here. 
Selected Publications (Click here for a full list)
Cluster before you Hallucinate: Approximating Node Capacitated Network Design
STOC 2014 (with V. Nagarajan, K. Pruhs and C. Stein) [pdf  ppt  ]
In this paper, we consider the following capacitated network design problem: we are given a collection of flow requirements between some pairs of vertices, and a graph G where each node has a cost c_v and of capacity q. The goal is choose the min. cost set of vertices so that the induced subgraph supports all the flow requirements. This very general problem captures problems such as node Steiner tree as a special case. We show the first nontrivial polylog approximation, with a polylogarithmic congestion on the vertices.
SODA 2014 (with A. Antoniadis, S. Im, B. Moseley, V. Nagarajan, K. Pruhs and C. Stein) [pdf  ppt  ]
In this paper, we consider the problems of capacitated network design and energy efficient routing: in the former, we are given a collection of flow requirements between some pairs of vertices, and a graph G where each edge has a cost c_e and of capacity q. The goal is choose the min. cost set of edges so that the induced subgraph supports all the flow requirements.
In the latter, the goal is to route all the demand to minimize the total energy of the routing (summed over all edges): the energy consumed on an edge is c_e + l(e)^{α}, where l(e) is the total flow routed on edge e. Andrews et al. [FOCS 2010] give a sophisticated algorithm which gives a polylogarithmic approximation algorithm for the offline version of the problem. We improve it on several directions: our algorithm is much simpler, gives much improved guarantees, and handles the online case where demands arrive over time.
SODA 2014 (with Nikhil Bansal, Moses Charikar and Shi Li) [pdf  ppt  ]
We consider the classical broadcast scheduling problem: requests arrive over time for unit sized pages, and when a page is broadcasted all unsatisfied requests for the page are satisfied. The goal is to find a broadcast schedule so as to minimize the total waiting time (aka flow time) of the requests. For nearly a decade, the best approximation algorithm has an approximation ratio of O(log^2 n). In this paper, we improve it to O(log^1.5 n), and also give the first hardness result, ruling out any constant factor approximation. Both these results are a byproduct of our main observation connecting the problem to that of minimizing the discrepancy of l permutations.
APPROX 2013 (with Deeparnab Chakrabarty and Shi Li and Srivatsan Narayanan) [pdf  ppt  ]
We consider the following capacitated network design problem: given a graph G (where edges have capacities), vertices s and t, and a flow requrement R, find the smallest cardinality subgraph (in terms of number of edges retained) which can support an st flow of at least R. While this problem has been studied for at least a decade, its approximability is still unresolved. In this paper, we show that the problem is in fact labelcover hard, i.e., hard to approximate to any subpolynomial factors. We also show the first logarithmic hardness for the source location problem along the way. A very interesting open question is designing bicriteria algorithms, which violates the R flow.
STOC 2012 (with Aditya Bhaskara, Daniel Dadush and Kunal Talwar) [pdf  ppt  ]
In this paper, we present unconditional and improved (w.r.t approximation on the noise) algorithms for differentially privately answering a system of linear queries. Prior mechanisms with provable guarantees relied upon a longstanding unresolved conjecture in convex geometry known as the hyperplane conjecture.
SODA 2012 (with Anupam Gupta, Viswanath Nagarajan, and R. Ravi) [pdf  ppt  o]
We consider the extension of the orienteering problem, but now there are random waiting times at nodes before we can collect reward. This therefore naturally generalizes the stochastic knapsack problem also, where there is a trivial metric of colocated jobs. While most earlier papers on such stochastic problems bound adaptivity gaps using an LP relaxation, we are unable to do so because we don't know of good LPs for just orienteering. We circumvent this by directly arguing about an adaptive solution using a Martingale analysis and are able to show an O(log log B)approximation algorithm and adaptivity gap.
FOCS 2011 (with Anupam Gupta, Marco Molinaro and R. Ravi) [pdf  o]
We extend the results of Dean, Goemans and Vondrak for the Stochastic Knapsack problem to one where the reward of an item may be correlated with the size it instantiates to, and give a constantfactor nonadaptive approximation algorithm. We use ideas for this problem and also present a constantfactor adaptive approximation algorithm for the general MultiArmed Bandits problem, relaxing certain Martingale property requirements of currently known algorithms.
STOC 2009 (with Anupam Gupta and R. Ravi) To appear in the SICOMP special issue [pdf  ppt  o]
Consider the following generalization of the online Steiner tree problem: each day, a new pair of vertices (s_{i},t_{i}) arrive requiring kedgeconnectivity; the objective is to buy a set of edges to kconnect these vertices such that the total cost of the edges bought till date is competitive with the cost of the optimal offline solution feasible to the pairs that have arrived. We give an online algorithm with polylogarithmic competitiveness, by using recent results on embeddings into subtrees to get more structure on the cuts.
Other Links Do check out my wife Divya's Indian coffee venture Madrush Coffee if you want fresh Indian coffees shipped across the USA. And if you host at Airbnb, check out Pricelabs, an exciting startup of my undergraduate friend Anurag! 