My research interests are in approximation algorithms, especially for graph-theoretic 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 non-trivial polylog approximation, with a polylogarithmic congestion on the vertices.
Hallucination Helps: Energy Effcient Virtual Circuit Routing
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.
Better Algorithms and Hardness for Broadcast Scheduling
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 by-product of our main observation connecting the problem to that of minimizing the discrepancy of l permutations.
Capacitated Network Design on Undirected Graphs
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 s-t 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 label-cover hard, i.e., hard to approximate to any sub-polynomial factors. We also show the first logarithmic hardness for the source location problem along the way. A very interesting open question is designing bi-criteria algorithms, which violates the R flow.
Unconditional Differentially Private Algorithms for Linear Queries
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 long-standing unresolved conjecture in convex geometry known as the hyperplane conjecture.
Approximation Algorithms for Stochastic Orienteering
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 co-located 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.
Approximation Algorithms for Correlated Knapsack and Non-Martingale Bandits
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 constant-factor non-adaptive approximation algorithm. We use ideas for this problem and also present a constant-factor adaptive approximation algorithm for the general Multi-Armed Bandits problem, relaxing certain Martingale property requirements of currently known algorithms.
Online and Stochastic Survivable Network Design
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 (si,ti) arrive requiring k-edge-connectivity; the objective is to buy a set of edges to k-connect 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.
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!