TY - JOUR T1 - Dependent rounding and its applications to approximation algorithms JF - Journal of the ACM Y1 - 2006 A1 - Gandhi,Rajiv A1 - Khuller, Samir A1 - Parthasarathy,Srinivasan A1 - Srinivasan, Aravind KW - broadcast scheduling KW - Randomized rounding AB - 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. VL - 53 SN - 0004-5411 UR - http://doi.acm.org/10.1145/1147954.1147956 CP - 3 M3 - 10.1145/1147954.1147956 ER -