Dependent rounding and its applications to approximation algorithms

Rajiv Gandhi*, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

148 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)324-360
Number of pages37
JournalJournal of the ACM
Volume53
Issue number3
DOIs
StatePublished - 2006

Keywords

  • Broadcast scheduling
  • Randomized founding

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Dependent rounding and its applications to approximation algorithms'. Together they form a unique fingerprint.

Cite this