Dependent rounding and its applications to approximation algorithms

DOI10.1145/1147954.1147956zbMath1312.68233OpenAlexW2007604989MaRDI QIDQ3546323

Srinivasan Parthasarathy, Aravind Srinivasan, Rajiv Gandhi, Samir Khuller

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1147954.1147956

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (38)

Approximation algorithms for stochastic combinatorial optimization problems ⋮ Random Walks in Polytopes and Negative Dependence ⋮ Improved Approximation Algorithms for Stochastic Matching ⋮ Improved Approximation Algorithm for Fault-Tolerant Facility Placement ⋮ An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation ⋮ A primal-dual approximation algorithm for partial vertex cover: Making educated guesses ⋮ An adaptive routing approach for personal rapid transit ⋮ Unnamed Item ⋮ An Experimental Study of Algorithms for Online Bipartite Matching ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ On the configuration LP for maximum budgeted allocation ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ Resource time-sharing for IoT applications with deadlines ⋮ Unnamed Item ⋮ Approximating the Interval Constrained Coloring Problem ⋮ Tight approximation algorithms for ordered covering ⋮ Component-by-component construction of low-discrepancy point sets of small size ⋮ Approximation algorithms for the interval constrained coloring problem ⋮ A PTAS for the cardinality constrained covering with unit balls ⋮ Iterative partial rounding for vertex cover with hard capacities ⋮ Capacitated Domination Problem ⋮ Proportional Approval Voting, Harmonic k-median, and Negative Association ⋮ A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem ⋮ The interval constrained 3-coloring problem ⋮ Improved bounds in stochastic matching and optimization ⋮ When LP is the cure for your matching woes: improved bounds for stochastic matchings ⋮ Capacitated domination problem ⋮ Online stochastic matching: new algorithms and bounds ⋮ Algorithmic construction of low-discrepancy point sets via dependent randomized rounding ⋮ Scheduling to minimize energy and flow time in broadcast scheduling ⋮ Unnamed Item ⋮ An improved derandomized approximation algorithm for the max-controlled set problem ⋮ Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts ⋮ Capacitated discrete unit disk cover ⋮ Randomized Rounding in the Presence of a Cardinality Constraint ⋮ An almost optimal approximation algorithm for monotone submodular multiple knapsack ⋮ Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines ⋮ Unnamed Item

Uses Software

• SPIDER

This page was built for publication: Dependent rounding and its applications to approximation algorithms