TY - CONF
T1 - Dependent rounding in bipartite graphs
T2 - The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
Y1 - 2002
A1 - Gandhi,R.
A1 - Khuller, Samir
A1 - Parthasarathy,S.
A1 - Srinivasan, Aravind
KW - Application software
KW - Approximation algorithms
KW - bipartite graph
KW - bipartite graphs
KW - broadcast channels
KW - broadcast scheduling
KW - Broadcasting
KW - capacitated vertex cover
KW - Character generation
KW - computational complexity
KW - Computer science
KW - Delay
KW - edge-sets
KW - Educational institutions
KW - fair scheduling
KW - fractional vectors
KW - graph theory
KW - per-user fairness properties
KW - pipage rounding technique
KW - Processor scheduling
KW - Random variables
KW - random-graph models
KW - randomized rounding approach
KW - rounding method
KW - scheduling
KW - Scheduling algorithm
KW - telecommunication computing
KW - unrelated parallel machines
AB - 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.
JA - The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings
PB - IEEE
SN - 0-7695-1822-2
M3 - 10.1109/SFCS.2002.1181955
ER -