@article {17549,
	title = {A unified approach to scheduling on unrelated parallel machines},
	journal = {J. ACM},
	volume = {56},
	year = {2009},
	month = {2009/08//},
	pages = {28:1{\textendash}28:31 - 28:1{\textendash}28:31},
	abstract = {We develop a single rounding algorithm for scheduling on unrelated parallel machines; this algorithm works well with the known linear programming-, quadratic programming-, and convex programming-relaxations for scheduling to minimize completion time, makespan, and other well-studied objective functions. This algorithm leads to the following applications for the general setting of unrelated parallel machines: (i) a bicriteria algorithm for a schedule whose weighted completion-time and makespan simultaneously exhibit the current-best individual approximations for these criteria; (ii) better-than-two approximation guarantees for scheduling to minimize the Lp norm of the vector of machine-loads, for all 1 < p < $\infty$; and (iii) the first constant-factor multicriteria approximation algorithms that can handle the weighted completion-time and any given collection of integer Lp norms. Our algorithm has a natural interpretation as a melding of linear-algebraic and probabilistic approaches. Via this view, it yields a common generalization of rounding theorems due to Karp et al. [1987] and Shmoys \& Tardos [1993], and leads to improved approximation algorithms for the problem of scheduling with resource-dependent processing times introduced by Grigoriev et al. [2007].},
	keywords = {Approximation algorithms, Randomized rounding, scheduling under multiple criteria},
	isbn = {0004-5411},
	doi = {10.1145/1552285.1552289},
	url = {http://doi.acm.org/10.1145/1552285.1552289},
	author = {Kumar,V. S. Anil and Marathe,Madhav V. and Parthasarathy,Srinivasan and Srinivasan, Aravind}
}
@article {15252,
	title = {Dependent rounding and its applications to approximation algorithms},
	journal = {Journal of the ACM},
	volume = {53},
	year = {2006},
	month = {2006/05//},
	pages = {324 - 360},
	abstract = {We develop a new randomized rounding approach for fractional vectors defined on the edge-sets of bipartite graphs. We show various ways of combining this technique with other ideas, leading to improved (approximation) algorithms for various problems. These include:---low congestion multi-path routing;---richer random-graph models for graphs with a given degree-sequence;---improved approximation algorithms for: (i) throughput-maximization in broadcast scheduling, (ii) delay-minimization in broadcast scheduling, as well as (iii) capacitated vertex cover; and---fair scheduling of jobs on unrelated parallel machines.},
	keywords = {broadcast scheduling, Randomized rounding},
	isbn = {0004-5411},
	doi = {10.1145/1147954.1147956},
	url = {http://doi.acm.org/10.1145/1147954.1147956},
	author = {Gandhi,Rajiv and Khuller, Samir and Parthasarathy,Srinivasan and Srinivasan, Aravind}
}
@article {15249,
	title = {An improved approximation algorithm for vertex cover with hard capacities},
	journal = {Journal of Computer and System Sciences},
	volume = {72},
	year = {2006},
	month = {2006/02//},
	pages = {16 - 33},
	abstract = {We study the capacitated vertex cover problem, a generalization of the well-known vertex-cover problem. Given a graph G = ( V , E ) , the goal is to cover all the edges by picking a minimum cover using the vertices. When we pick a vertex, we can cover up to a pre-specified number of edges incident on this vertex (its capacity). The problem is clearly NP-hard as it generalizes the well-known vertex-cover problem. Previously, approximation algorithms with an approximation factor of 2 were developed with the assumption that an arbitrary number of copies of a vertex may be chosen in the cover. If we are allowed to pick at most a fixed number of copies of each vertex, the approximation algorithm becomes much more complex. Chuzhoy and Naor (FOCS, 2002) have shown that the weighted version of this problem is at least as hard as set cover; in addition, they developed a 3-approximation algorithm for the unweighted version. We give a 2-approximation algorithm for the unweighted version, improving the Chuzhoy{\textendash}Naor bound of three and matching (up to lower-order terms) the best approximation ratio known for the vertex-cover problem.},
	keywords = {Approximation algorithms, Capacitated covering, Linear programming, Randomized rounding, Set cover, Vertex cover},
	isbn = {0022-0000},
	doi = {10.1016/j.jcss.2005.06.004},
	url = {http://www.sciencedirect.com/science/article/pii/S0022000005000747},
	author = {Gandhi,Rajiv and Halperin,Eran and Khuller, Samir and Kortsarz,Guy and Srinivasan, Aravind}
}
@article {17561,
	title = {Approximation algorithms for partial covering problems},
	journal = {Journal of Algorithms},
	volume = {53},
	year = {2004},
	month = {2004/10//},
	pages = {55 - 84},
	abstract = {We study a generalization of covering problems called partial covering. Here we wish to cover only a desired number of elements, rather than covering all elements as in standard covering problems. For example, in k-partial set cover, we wish to choose a minimum number of sets to cover at least k elements. For k-partial set cover, if each element occurs in at most f sets, then we derive a primal-dual f-approximation algorithm (thus implying a 2-approximation for k-partial vertex cover) in polynomial time. Without making any assumption about the number of sets an element is in, for instances where each set has cardinality at most three, we obtain an approximation of 4/3. We also present better-than-2-approximation algorithms for k-partial vertex cover on bounded degree graphs, and for vertex cover on expanders of bounded average degree. We obtain a polynomial-time approximation scheme for k-partial vertex cover on planar graphs, and for covering k points in Rd by disks.},
	keywords = {Approximation algorithms, Partial covering, Primal-dual methods, Randomized rounding, Set cover, Vertex cover},
	isbn = {0196-6774},
	doi = {10.1016/j.jalgor.2004.04.002},
	url = {http://www.sciencedirect.com/science/article/pii/S0196677404000689},
	author = {Gandhi,Rajiv and Khuller, Samir and Srinivasan, Aravind}
}
@conference {17545,
	title = {A constant-factor approximation algorithm for packet routing, and balancing local vs. global criteria},
	booktitle = {Proceedings of the twenty-ninth annual ACM symposium on Theory of computing},
	series = {STOC {\textquoteright}97},
	year = {1997},
	month = {1997///},
	pages = {636 - 643},
	publisher = {ACM},
	organization = {ACM},
	address = {New York, NY, USA},
	keywords = {Approximation algorithms, covering integer programs, discrete ham-sandwich theorems, Linear programming, packet routing, randomized algorithms, Randomized rounding, rounding theorems},
	isbn = {0-89791-888-6},
	doi = {10.1145/258533.258658},
	url = {http://doi.acm.org/10.1145/258533.258658},
	author = {Srinivasan, Aravind and Teo,Chung-Piaw}
}
