Publications

Home

Naveen Garg, Telikepalli Kavitha,  Amit Kumar,  Kurt Mehlhorn and Julian Mestre[link]
Assigning Papers to Referees
Algorithmica (accepted for publication)

Refereed conferences require every submission to be reviewed by members of a program committee (PC) in charge of selecting the conference program. There are many software packages available to manage the review process. Typically, in a bidding phase PC members express their personal preferences by ranking the submissions. This information is used by the system to compute an assignment of the papers to referees (PC
members).
We study the problem of assigning papers to referees. We propose to optimize a number of criteria that aim at achieving fairness among referees/papers. Some of these variants can be solved optimally in polynomial time, while others are NP-hard, in which case we design approximation algorithms. Experimental results strongly suggest that the assignments computed by our algorithms are considerably better than those computed by popular conference management software.

Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, Danny Segev
Scheduling with Outliers.
APPROX-RANDOM 2009

In classical scheduling problems, we are given jobs and machines, and have to schedule all the jobs to minimize some objective function. What if each job has a specified profit, and we are no longer required to process all jobs? Instead, we can schedule any subset of jobs whose total profit is at least a (hard) target profit requirement, while still trying to approximately minimize the objective function.
We refer to this class of problems as scheduling with outliers. This model was initiated by Charikar and Khuller (SODA ’06) for minimum max-response time in broadcast scheduling. In this paper, we consider three other well-studied scheduling objectives: the generalized assignment problem, average weighted completion time, and average flow time, for which LP-based approximation algorithms are provided. Our main results are:
  For the minimum average flow time problem on identical machines, we give an LP-based logarithmic approximation algorithm for the unit profits case, and complement this result by presenting a matching integrality gap.
  For the average weighted completion time problem on unrelated machines, we give a constant-factor approximation. The algorithm is based on randomized rounding of the time-indexed LP relaxation strengthened by knapsack-cover inequalities.
  For the generalized assignment problem with outliers, we outline a simple reduction to GAP without outliers to obtain an algorithm whose makespan is within 3 times the optimum makespan, and whose cost is at most (1 + ε) times the optimal cost.

Anupam Gupta, Amit Kumar
A constant-factor approximation for stochastic Steiner forest.
STOC 2009

We consider the stochastic Steiner forest problem: suppose we were given a collection of Steiner forest instances, and were guaranteed that a random one of these instances would appear tomorrow; moreover, the cost of edges tomorrow will be λ times the cost of edges today. Which edges should we buy today so that we can extend it to a solution for the instance arriving tomorrow, to minimize the expected total cost? While very general results have been developed for many problems in stochastic discrete optimization over the past years, the approximation status of the stochastic Steiner Forest problem has remained open, with previous works yielding constant-factor approximations only for special cases. We resolve the status of this problem by giving a constant-factor primal-dual based approximation algorithm.

Jivitej S. Chadha, Naveen Garg, Amit Kumar, V. N. Muralidhara
A competitive algorithm for minimizing weighted flow time on unrelated machines with speed augmentation.
STOC 2009

We consider the online problem of scheduling jobs on unrelated machines so as to minimize the total weighted flow time. This problem has an unbounded competitive ratio even for very restricted settings. In this paper we show that if we allow the machines of the online algorithm to have ε more speed than those of the offline algorithm then we can get an O((1+ε-1)2)-competitive algorithm. Our algorithm schedules jobs preemptively but without migration. However, we compare our solution to an offline algorithm which allows migration. Our analysis uses a potential function argument which can also be extended to give a simpler and better proof of the randomized immediate dispatch algorithm of Chekuri-Goel-Khanna-Kumar for minimizing average flow time on parallel machines.

Naveen Garg, Amit Kumar, V. N. Muralidhara:
Minimizing Total Flow-Time: The Unrelated Case [link]
ISAAC 2008

We consider the problem of minimizing flow-time in the unrelated machines setting. We introduce a notion of (α,β) variability to capture settings where processing times of jobs on machines are not completely arbitrary and give an O(βlogα) approximation for this setting. As special cases, we get (1) an O(k) approximation when there are only k different processing times (2) an O(logP)-approximation if each job can only go on a specified subset of machines, but has the same processing requirement on each such machine. Further, the machines can have different speeds. Here P is the ratio of the largest to the smallest processing requirement, (3) an - approximation algorithm for unrelated machines if we assume that our algorithm has machines which are an ε-factor faster than the optimum algorithm’s machines. We also improve the lower bound on the approximability for the problem of minimizing flow time on parallel machines from $\Omega(\sqrt{\log P/ \log\log P})$ to Ω(log1 − ε P) for any ε>0.

Daniel Golovin, Anupam Gupta, Amit Kumar, Kanat Tangwongsan
All-Norms and All-L_p-Norms Approximation Algorithms.
FSTTCS 2008

In many optimization problems, a solution can be viewed as ascribing a "cost" to each client, and the goal is to optimize some aggregation of the per-client costs. We often optimize some $L_p$-norm (or some other symmetric convex function or norm) of the vector of costs---though different applications may suggest different norms to use. Ideally, we could obtain a solution that optimizes several norms simultaneously. In this paper, we examine approximation algorithms that simultaneously perform well on all norms, or on all $L_p$ norms. A natural problem in this framework is the $L_p$ Set Cover problem, which generalizes Set Cover and Min-Sum Set Cover. We show that the greedy algorithm simultaneously gives a $(p + \ln p + O(1))$-approximation for all $p$, and show that this approximation ratio is optimal up to constants under reasonable complexity-theoretic assumptions. We additionally show how to use our analysis techniques to give similar results for the more general submodular set cover, and prove some results for the so-called pipelined set cover problem. We then go on to examine approximation algorithms in the "all-norms" and the "all-$L_p$-norms" frameworks more broadly, and present algorithms and structural results for other problems such as $k$-facility-location, TSP, and average flow-time minimization, extending and unifying previously known results.

Naveen Garg and Anupam Gupta and Stefano Leonardi and Piotr Sankowski
Stochastic Analyses for Online Combinatorial Optimization Problems [link]
SODA 2008

In this paper, we study online algorithms when the input is not chosen adversarially, but consists of draws from some given probability distribution. While this model has been studied for online problems like paging and k-server, it is not known how to beat the (log n) bound for online Steiner tree if at each time instant, the demand vertex is a uniformly random vertex from the graph. For the online Steiner tree problem, we show that if each demand vertex is an independent draw from some probability distribution  a variant of the natural greedy algorithm achieves a constant competitive ratio; moreover, this result can be extended to some other subadditive problems. Both assumptions that the input sequence consists of independent draws from , and that is known to the
algorithm are both essential; we show (almost) logarithmic lower bounds if either assumption is violated.
 

Naveen Garg, Amit Kumar and Vinayaka Pandit.
Order Scheduling Models: Hardness and Algorithms [link]
FSTTCS 2007

We consider scheduling problems in which a job consists of components of different types to be processed on m machines. Each machine is capable of processing components of a single type. Different components of a job are independent and can be processed in parallel on different machines. A job is considered as completed only when all its components have been completed. We study both completion time and flowtime aspects of such problems. We show both lower bounds and upper bounds for the completion time problem. We first show that even the unweighted completion time with single release date is MAX-SNP hard. We give an approximation algorithm based on linear programming which has an approximation ratio of 3 for weighted completion time with multiple release dates. We give online algorithms for the weighted completion time which are constant factor competitive. For the flowtime, we give only lowerbounds in both the offline and online settings. We show that it is NP-hard to approximate flowtime within (logm) in the offline setting. We show that no online algorithm for the flowtime can have a competitive ratio better than \sqrt{m}.

Amit Kumar and Yogish Sabharwal
The Priority K-median Problem
FSTTCS, 2007.

In this paper, we consider a generalized version of the k-median problem in metric spaces, called the priority k-median problem in which demands and facilities have priorities associated with them and a demand can only be assigned to a facility that has the same priority or better. We show that there exists a polynomial time constant factor approximation algorithm for this problem when there are two priorities. We also show that the natural integer program for the problem has an arbitrarily large integrality gap when there are four or more priorities.

Naveen Garg and Amit Kumar
Minimizing Average Flow-time : Upper and Lower Bounds
[link]
FOCS 2007

We consider the problem of minimizing average flow time on multiple machines when each job can be assigned only to a specified subset of the machines. This is a special case of scheduling on unrelated machines and we show that no online algorithm can have a bounded competitive ratio. We provide an O(log P)-approximation algorithm by modifying the single-source unsplittable flow algorithm of Dinitz et.al. Here P  is the ratio of the maximum to the minimum processing times. We establish an (log P)-integrality gap for our LP-relaxation and use this to show an (log P/log log P) lower bound on the approximability of the problem. We then extend the hardness results to the problem of minimizing flow time on parallel machines and establish the first non-trivial lower bounds on the approximability; we show that the problem cannot be approximated to within \sqrt{log P/log log P}.

Anupam Gupta, MohammadTaghi Hajiaghayi, Amit Kumar
Steiner Tree with Non-uniform Inflation [link]
APPROX-RANDOM 2007

We study the Steiner Tree problem in the model of two-stage stochastic optimization with non-uniform inflation factors, and give a poly-logarithmic approximation factor for this problem. We complement our results by showing that our problem is at least as hard as the single-sink Cost-Distance problem (which is known to be Ω(loglogn) hard). As an aside, we also give an LP-rounding algorithm for the multi-commodity Cost-Distance problem, matching the O(log4 n) approximation guarantee given by Chekuri et al. (FOCS 2006).

Naveen Garg and Amit Kumar
Better Algorithms for Minimizing Average Flow-Time on Related Machines [link]
International Colloquium on Automata Languages and Programming  2006

We consider the problem of minimising flow time on related machines and give an O(logP)-approximation algorithm for the offline case and an O(log2P)-competitive algorithm for the online version. This improves upon the previous best bound of O(log2P logS) on the competitive ratio. Here P is the ratio of the maximum to the minimum processing time of a job and S is the ratio of the maximum to the minimum speed of a machine.

Naveen Garg and Amit Kumar
Minimizing average flow time on related machines [link]
35th Annual ACM Symposium on Algorithms

We give the first on-line poly-logarithmic competitve algorithm for minimizing average flow time with preemption on related machines, i.e., when machines can have different speeds. This also yields the first poly-logarithmic polynomial time approximation algorithm for this problem.More specifically, we give an O(log2 P • log S)-competitive algorithm, where P is the ratio of the biggest and the smallest processing time of a job, and S is the ratio of the highest and the smallest speed of a machine. Our algorithm also has the nice property that it is non-migratory. The scheduling algorithm is based on the concept of making jobs wait for a long enough time before scheduling them on slow machines.

Nikhil R. Devanur, Naveen Garg, Rohit Khandekar, Vinayaka Pandit, Amin Saberi, Vijay V. Vazirani
Price of Anarchy, Locality Gap, and a Network Service Provider Game [link]
Workshop on Internet and Network Economics 2005

In this paper, we define a network service provider game. We show that the price of anarchy of the defined game can be bounded by analyzing a local search heuristic for a related facility location problem called the k-facility location problem. As a result, we show that the k-facility location problem has a locality gap of 5. This result is of interest on its own. Our result gives evidence to the belief that the price of anarchy of certain games are related to analysis of local search heuristics.

Garima Batra, Naveen Garg  and Garima Gupta
Heuristic improvements for computing max multicommodity flow and min multicut [link]
13th European Symposium on Algorithms, 2005

We propose heuristics to reduce the number of shortest path computations required to compute a 1+ε approximation to the maximum multicommodity flow in a graph. Through a series of improvements we are able to reduce the number of shortest path computations significantly. One key idea is to use the value of the best multicut encountered in the course of the algorithm. For almost all instances this multicut is significantly better than that computed by rounding the linear program.