Title: Dependent rounding and its applications to approximation algorithms
Abstract: 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.
Publication Year: 2006
Publication Date: 2006-05-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 263
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot