loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Dependent Rounding in Bipartite Graphs
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
ASCII Text
x 
 
Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan, "Dependent Rounding in Bipartite Graphs," Foundations of Computer Science, IEEE Annual Symposium on, pp. 323, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002.
 
 
BibTex
x
 
@article{ 10.1109/SFCS.2002.1181955,
author = {Rajiv Gandhi and Samir Khuller and Srinivasan Parthasarathy and Aravind Srinivasan},
title = {Dependent Rounding in Bipartite Graphs},
journal ={Foundations of Computer Science, IEEE Annual Symposium on},
volume = {0},
year = {2002},
issn = {0272-5428},
pages = {323},
doi = {http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181955},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, IEEE Annual Symposium on
TI - Dependent Rounding in Bipartite Graphs
SN - 0272-5428
SP
EP
A1 - Rajiv Gandhi,
A1 - Samir Khuller,
A1 - Srinivasan Parthasarathy,
A1 - Aravind Srinivasan,
PY - 2002
KW - null
VL - 0
JA - Foundations of Computer Science, IEEE Annual Symposium on
ER -
 
Rajiv Gandhi, University of Maryland at College Park
Samir Khuller, University of Maryland at College Park
Srinivasan Parthasarathy, University of Maryland at College Park
Aravind Srinivasan, University of Maryland at College Park

We combine the pipage rounding technique of Ageev & Sviridenko with a recent rounding method developed by Srinivasan, 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.

    Citation:
    Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan, "Dependent Rounding in Bipartite Graphs," focs, pp.323, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
    Usage of this product signifies your acceptance of the Terms of Use.