Dependent rounding and its applications to approximation algorithms

2006/05/01 by Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy +1 · 26 citations
Computer Science · #Complexity and Algorithms in Graphs #Optimization and Search Problems #Advanced Graph Theory Research

paper · doi: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.

Cited by

• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Online Service Placement and Request Scheduling in MEC Networks
• Combinatorial Semi-Bandits with Knapsacks
• Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
• ADAM Optimization with Adaptive Batch Selection
• Near-Optimal Dropout-Robust Sortition
• Randomized Rounding over Dynamic Programs
• Improved Online Load Balancing in the Two-Norm
• Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models
• Optimal Rounding for Two-Stage Bipartite Matching
• Online Scaling of NFV Service Chains Across Geo-Distributed Datacenters
• Dependent Randomized Rounding for Matroid Polytopes and Applications
• Probabilistic Fair Clustering
• When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
• In This Apportionment Lottery, the House Always Wins
• Towards Heterogeneity-Aware and Energy-Efficient Topology Optimization for Decentralized Federated Learning in Edge Environment
• Low-Regret Active learning
• On Sharing Private Data with Multiple Non-Colluding Adversaries
• Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems
• Unknown Delay for Adversarial Bandit Setting with Multiple Play
• Best-of-Both-Worlds Guarantees with Fairer Endings
• A New Approximation Technique for Resource-Allocation Problems
• Online Scheduling to Minimize the Maximum Delay Factor
• Drawing a map of elections
• A few good choices
• Group-level Fairness Maximization in Online Bipartite Matching

Related

• Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
• Randomized Rounding for Routing and Covering Problems: Experiments and Improvements
• A note on rounding fractional matchings with constant-factor strong negative correlation
• A Note on Rounding Matchings in General Graphs
• Approximation-Friendly Discrepancy Rounding