Dependent rounding and its applications to approximation algorithms

TitleDependent rounding and its applications to approximation algorithms
Publication TypeJournal Articles
Year of Publication2006
AuthorsGandhi R, Khuller S, Parthasarathy S, Srinivasan A
JournalJournal of the ACM
Pagination324 - 360
Date Published2006/05//
ISBN Number0004-5411
Keywordsbroadcast scheduling, Randomized rounding

We 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 improved (approximation) algorithms for various problems. These include:---low congestion multi-path routing;---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, as well as (iii) capacitated vertex cover; and---fair scheduling of jobs on unrelated parallel machines.