@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}
}
@conference {17583,
	title = {Dependent rounding in bipartite graphs},
	booktitle = {The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings},
	year = {2002},
	month = {2002///},
	pages = {323 - 332},
	publisher = {IEEE},
	organization = {IEEE},
	abstract = {We combine the pipage rounding technique of Ageev \& Sviridenko with a recent rounding method developed by Srinivasan (2001), to 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 the following applications: 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, and (iii) capacitated vertex cover; fair scheduling of jobs on unrelated parallel machines. A useful feature of our method is that it lets us prove certain (probabilistic) per-user fairness properties.},
	keywords = {Application software, Approximation algorithms, bipartite graph, bipartite graphs, broadcast channels, broadcast scheduling, Broadcasting, capacitated vertex cover, Character generation, computational complexity, Computer science, Delay, edge-sets, Educational institutions, fair scheduling, fractional vectors, graph theory, per-user fairness properties, pipage rounding technique, Processor scheduling, Random variables, random-graph models, randomized rounding approach, rounding method, scheduling, Scheduling algorithm, telecommunication computing, unrelated parallel machines},
	isbn = {0-7695-1822-2},
	doi = {10.1109/SFCS.2002.1181955},
	author = {Gandhi,R. and Khuller, Samir and Parthasarathy,S. and Srinivasan, Aravind}
}
