Dependent rounding in bipartite graphs
- 26 June 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 323-332
- https://doi.org/10.1109/sfcs.2002.1181955
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.Keywords
This publication has 10 references indexed in Scilit:
- Throughput maximization of real-time scheduling with batchingACM Transactions on Algorithms, 2009
- Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance GuaranteeJournal of Combinatorial Optimization, 2004
- Covering problems with hard capacitiesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A general model of web graphsRandom Structures & Algorithms, 2003
- Algorithms for Minimizing Response Time in Broadcast SchedulingPublished by Springer Nature ,2002
- Crawling on web graphsPublished by Association for Computing Machinery (ACM) ,2002
- New Algorithmic Aspects of the Local Lemma with Applications to Routing and PartitioningSIAM Journal on Computing, 2001
- Distributions on level-sets with applications to approximation algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- A unified approach to approximating resource allocation and schedulingPublished by Association for Computing Machinery (ACM) ,2000
- Approximation algorithms for scheduling unrelated parallel machinesMathematical Programming, 1990