@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} }