Dependent rounding in bipartite graphs
| Title | Dependent rounding in bipartite graphs |
| Publication Type | Conference Papers |
| Year of Publication | 2002 |
| Authors | Gandhi R, Khuller S, Parthasarathy S, Srinivasan A |
| Conference Name | The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings |
| Date Published | 2002/// |
| Publisher | IEEE |
| ISBN Number | 0-7695-1822-2 |
| 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 |
| 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. |
| DOI | 10.1109/SFCS.2002.1181955 |