Dependent rounding and its applications to approximation algorithms
From MaRDI portal
Publication:3546323
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
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
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
