Cluster before you Hallucinate: Approximating Node Capacitated Network Design
STOC 2014 (with V. Nagarajan, K. Pruhs and C. Stein)
[pdf | ppt | ] (network-design, approx-algos, flows)
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 | ] (network-design, flows, online-algos, energy)
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 via a Discrepancy Approach
SODA 2014 (with Nikhil Bansal, Moses Charikar and Shi Li)
[pdf | ppt | ] (scheduling, approx-algos, discrepancy)
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.2013
On Capacitated Network Design: Hardness and Algorithms
APPROX 2013 (with D. Chakrabarty, S. Li and S. Narayanan)
[pdf | ppt | ] (network-design, approx-algos, flows, hardness)
In this paper, we show that the capacitated network design problem is Label-Cover hard. Here, we are given a capacitated graph G and two vertices s and t. The goal is to find the smallest subgraph H of G so that s can route R units of flow to t. We also show a flow-additivity theorem for undirected graphs which, somewhat surprisingly, shows that the max flow between a set of vertices to a sink t is at least half the sum of the individual flows of these vertices (provided the set is minimal)
Approximation Algorithms for Minimizing Makespan on Low-Rank Processing Times
SODA 2013 (with Aditya Bhaskara, Kunal Talwar and Udi Wieder)
[pdf | ppt | ] (scheduling, approx-algos)
In this paper, we initiate the study of scheduling on unrelated machines, where the processing times p_ij (to schedule job j on machine i) forms a low-rank matrix. This captures a variety of scheduling problems, such as one where each machine has a vector of resources (speed, memory, bandwidth, etc.) and each job has a requirement of each of these resources and the running time is the inner product of these vectors. While a PTAS is known for rank 1, and APX-hardness is known for rank n, we investigate the region in between. In particular, we show that the problem is APX-hard even for rank 4 matrices, and show that it is unlikely to hard when the rank is 2 by obtaining a quasi-PTAS. The case of rank 3 is open.2012
Unconditional Differentially Private Mechanisms for Linear Queries
Inapproximability Results for the Multi-Level Facility Location Problem
Approximation Algorithms for Stochastic Orienteering2011
SODA 2012 (with Anupam Gupta, Viswanath Nagarajan, and R. Ravi)
[pdf | ppt | o] (stochastic-algos, approx-algos, network-design)
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.
Better Algorithms for Correlated Stochastic Knapsack and Non-Martingale Bandits
FOCS 2011 (with Anupam Gupta, Marco Molinaro and R. Ravi)
[pdf | o] (stochastic-algos, scheduling, approx-algos, bandits)
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.
On Capacitated Set Cover Problems
APPROX 2011 (with Nikhil Bansal and Barna Saha)
[pdf | ppt | o] (approx-algos, integrality-gaps, epsilon-nets)
We show that if a set system has hereditary approximation ratio of A (i.e., approximation ratio of any subsystem is also A), then its priority covering problem has an A log2 k approximation algorithm. In particular such set systems admit an A log log2 C approximation algorithm for the capacitated set cover problem where C is the maximum capacity of any set. We also show that this is tight upto log log C factor.
The Matroid Median Problem2010
SODA 2011 (with Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal and Barna Saha)
[pdf | o] (k-median, approx-algos, matroids)
In the classic k-median problem, given a metric space, we are required to open k centers to minimize the total cost of connecting each client to the nearest open center. What if the vertices belonged to L color classes, and there are different budgets on the number of centers that can be opened in each color class? For example, if there are 2 color classes, then the constraint would be to open r red centers and b blue centers, and the objective is again to minimize the total cost of connecting each client to the nearest open center (clients don't have any colors). In this paper, we give a constant approximation for this, and the more general setting where the open centers have to form an independent set of a given matroid. The technique involves sparsifying an LP solution, to reduce it to a feasible solution of another LP which almost resembles matroid intersection, which is an integral polytope.
Network-Wide Deployment of Intrusion Detection and Prevention Systems
Better Scalable Algorithms for Broadcast Scheduling
ICALP 2010 (with Nikhil Bansal and Viswanath Nagarajan)
[pdf | ppt | o] (scheduling, approx-algos, online-algos)
In the broadcast scheduling problem, there are a set of n pages, and requests for these arrive online. The server can broadcast pages at a fixed speed, and with any broadcast of some page, all pending requests for that page get satisfied. The goal is then to minimize the average response time of the requests. In this paper, we give an O(1 + ε)-speed O(1/ε2)-competitive online algorithm for the general problem with arbitrary page sizes.
Non-Clairvoyantly Scheduling Power Heterogeneous Processors
Scalably Scheduling Power-Heterogeneous Processors
ICALP 2010 (with Anupam Gupta and Kirk Pruhs)
[pdf | ppt | o] (scheduling, online-algos, energy)
We give an online speed-scaling algorithm which achieves constant competitiveness with (1 + ε)-speed augmentation for the problem of scheduling jobs on non-identical machines with each machine having an arbitrary power function, for the objective function of total flow time plus energy consumed.
Scheduling Jobs with Varying Parallelizability to Reduce Variance
SPAA 2010 (with Anupam Gupta, Sungjin Im, Benjamin Moseley and Kirk Pruhs)
[pdf | o] (scheduling, online-algos, energy)
We give an online algorithm which achieves constant competitiveness with (p + ε)-speed augmentation for the problem of non-clairvoyantly scheduling jobs with different degrees of parallelism on identical machines, with the objective of minimizing the Lp norm of flowtimes.
A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover
SODA 2010 (with Nikhil Bansal and Anupam Gupta)
[pdf | ppt | o] (scheduling, approx-algos, set-cover)
Consider the generalized min-sum set cover problem: we are given a universe of elements and a collection of subsets. Each subset S also has a requirement K(S). The goal is to output an ordering of the universe so that the total cover time of the sets is minimized, where the cover time of a set S is the earliest position in the order when K(S) elements from S have been output. We give a constant-factor approximation algorithm for this problem via rounding of a strengthened LP relaxation.
Tree Embeddings for Two-Edge-Connected Network Design2009
SODA 2010 (with Anupam Gupta and R. Ravi)
[pdf | ppt | o] (network-design, approx-algos, metric-embeddings)
In this paper, we look at the 2-edge-connectivity generalization of the problems: (i) group Steiner tree (now we want to choose representatives from each group and 2-connect them to the root), (ii) connected facility location (the facilities need to be 2-edge-connected), (iii) buy-at-bulk (the demand pairs need 2-edge-disjoint paths), and (iv) k-MST (pick an arbitrary set of k vertices and 2-connect them). We show that tree embedding techniques can be used to simplify all these problems and obtain polylogarithmic approximations.
Online and Stochastic Survivable Network Design
STOC 2009 (with Anupam Gupta and R. Ravi) Journal version in the SICOMP special issue for STOC.
[pdf | ppt | o] (network-design, online-algos, metric-embeddings)
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.
Scheduling with Outliers2007
APPROX 2009 (with Anupam Gupta, Amit Kumar and Danny Segev)
[pdf | arXiv | ppt | o] (scheduling, approx-algos)
In this paper, we study scheduling problems with the added flexibility of not picking a small fraction of jobs. Formally, given a set of jobs (each with an associated profit) and an objective function (like maximum makespan, average completion time, or average flow time), the goal is to schedule a subset of jobs that achieve some target profit, while minimizing the objective function on those set of jobs.
Fault Tolerant Network Coding