Dependent rounding and its applications to approximation algorithms

346 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, neutral): “2) to NO((1/ ) log(1/ )).”
Fair Allocation of Indivisible Public Goods (2018, methodology): “n of the core. We now show the existence of an approximate core solution. We begin with the fractional core outcome x that can be computed using ﬁxed point methods [13, 11]. We use dependent rounding [14] to roundP x to X so that (i) xj = E[Xj] for each element j; (ii) the constraint j Xj ≤B is pres”
Bandit Samplers for Training Graph Neural Networks (2020, methodology): “(2) In the adversary MAB with multiple plays setting [19], it uses an efficient k-combination sampler (DepRound [10]) Q to sample any k-element subset S ⊂ {1, 2, .”
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract) (2007, background): “A number of applications are given in [1,17,15].”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, background): “The original forms of pipage rounding [1] and dependent randomized rounding [40, 20] address the question of rounding a fractional solution to the assignment problem, while maintaining the quality of the solution in terms of a certain objective function.”