Dependent rounding and its applications to approximation algorithms
Top Cited Papers
- 1 May 2006
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 53 (3) , 324-360
- https://doi.org/10.1145/1147954.1147956
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.Keywords
This publication has 18 references indexed in Scilit:
- Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance GuaranteeJournal of Combinatorial Optimization, 2004
- NP-Hardness of Broadcast Scheduling and Inapproximability of Single-Source Unsplittable Min-Cost FlowJournal of Scheduling, 2004
- Crawling on Simple Models of Web GraphsInternet Mathematics, 2004
- Algorithms for Minimizing Response Time in Broadcast SchedulingAlgorithmica, 2003
- Capacitated vertex coveringJournal of Algorithms, 2003
- A general model of web graphsRandom Structures & Algorithms, 2003
- Optical network design and restorationBell Labs Technical Journal, 2002
- A new rounding procedure for the assignment problem with applications to dense graph arrangement problemsMathematical Programming, 2002
- A unified approach to approximating resource allocation and schedulingJournal of the ACM, 2001
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding BoundsSIAM Journal on Computing, 1997