Dependent rounding and its applications to approximation algorithms
From MaRDI portal
Publication:3546323
DOI10.1145/1147954.1147956zbMath1312.68233MaRDI 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
90B35: Deterministic scheduling theory in operations research
68M20: Performance evaluation, queueing, and scheduling in the context of computer systems
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Random Walks in Polytopes and Negative Dependence, Unnamed Item, Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, Unnamed Item, Proportional Approval Voting, Harmonic k-median, and Negative Association, An improved derandomized approximation algorithm for the max-controlled set problem, Capacitated Domination Problem, Unnamed Item, Unnamed Item, Capacitated discrete unit disk cover, A (1-e^{-1}-ε)-Approximation for the Monotone Submodular Multiple Knapsack Problem, An Experimental Study of Algorithms for Online Bipartite Matching, Resource time-sharing for IoT applications with deadlines, Approximation algorithms for stochastic combinatorial optimization problems, Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms, Geometric rounding: A dependent randomized rounding scheme, The interval constrained 3-coloring problem, Capacitated domination problem, Approximation algorithms for the interval constrained coloring problem, When LP is the cure for your matching woes: improved bounds for stochastic matchings, Algorithmic construction of low-discrepancy point sets via dependent randomized rounding, On the configuration LP for maximum budgeted allocation, Improved bounds in stochastic matching and optimization, Online stochastic matching: new algorithms and bounds, Scheduling to minimize energy and flow time in broadcast scheduling, An almost optimal approximation algorithm for monotone submodular multiple knapsack, Iterative partial rounding for vertex cover with hard capacities, Attenuate locally, win globally: attenuation-based frameworks for online stochastic matching with timeouts, A primal-dual approximation algorithm for partial vertex cover: Making educated guesses, An adaptive routing approach for personal rapid transit, A PTAS for the cardinality constrained covering with unit balls, Randomized Rounding in the Presence of a Cardinality Constraint, An Approximation Algorithm for Uniform Capacitated k-Median Problem with $$1+\epsilon $$ Capacity Violation, Improved Approximation Algorithms for Stochastic Matching, Improved Approximation Algorithm for Fault-Tolerant Facility Placement, Approximating the Interval Constrained Coloring Problem, Component-by-component construction of low-discrepancy point sets of small size
Uses Software
