%0 Conference Paper
%B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
%D 2002
%T Dependent rounding in bipartite graphs
%A Gandhi,R.
%A Khuller, Samir
%A Parthasarathy,S.
%A Srinivasan, Aravind
%K Application software
%K Approximation algorithms
%K bipartite graph
%K bipartite graphs
%K broadcast channels
%K broadcast scheduling
%K Broadcasting
%K capacitated vertex cover
%K Character generation
%K computational complexity
%K Computer science
%K Delay
%K edge-sets
%K Educational institutions
%K fair scheduling
%K fractional vectors
%K graph theory
%K per-user fairness properties
%K pipage rounding technique
%K Processor scheduling
%K Random variables
%K random-graph models
%K randomized rounding approach
%K rounding method
%K scheduling
%K Scheduling algorithm
%K telecommunication computing
%K unrelated parallel machines
%X 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.
%B The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
%I IEEE
%P 323 - 332
%8 2002///
%@ 0-7695-1822-2
%G eng
%R 10.1109/SFCS.2002.1181955