loading...
Dependent Rounding in Bipartite Graphs
Vancouver, BC, Canada November 16-November 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181955The 43rd Annual IEEE Symposium on Fou ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan, "Dependent Rounding in Bipartite Graphs," Foundations of Computer Science, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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, Annual IEEE 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.