Randomized rounding: A technique for provably good algorithms and algorithmic proofs

By Prabhakar Raghavan, Clark D. Thomborson. 1987

How researchers see this paper

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

Citations in the corpus

Strongly agree or strongly disagree?: Rating features in Support Vector Machines (2016, background): “The feature `having a guarantor' still strongly contributes to being a good customer, but `having a co-applicant' now contributes negatively (but not strongly), while `having no debtor' is still irrelevant.”
The Design of Competitive Online Algorithms via a Primal-Dual Approach (2009, methodology): “2 along with an online derandomization of the rounding method in [85, 86].”
The Design of Approximation Algorithms (2011, background): “Raghavan and Thompson [247] were the first to introduce the idea of the randomized rounding of a linear programming relaxation.”
FireFly (2014, methodology): “From this solution, we use the “path stripping” idea [42] to convert the values of the f i,j a,b variables into end-to-end paths.”
Rounding Methods for Discrete Linear Classification (2013, methodology): “Besides the Randomized Rounding (RR) algorithm and the Greedy Rounding (GR) algorithm, we evaluated the behavior of two fractional optimization techniques: the Convex (Cvx) optimization method that returns the fractional solution of the problem specified by (5), and the Support Vector Machine (L1-SV”
Bernstein-like Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case (2011, background): “Previous work by Kim-Vu and Schudy-Sviridenko gave bounds of the same form that involved less natural parameters in place of the variance.”
Virtual Network Embedding with Coordinated Node and Link Mapping (2009, unknown): “Techniques of randomized rounding for linear programming relaxations to obtain approximation algorithms was first introduced in [16].”
The Multiplicative Weights Update Method: a Meta-Algorithm and Applications (2012, methodology): “For many NP -hard problems, typically integer versions of packing-covering problems, one can compute a O ( log n ) -approximation by solving the obvious LP relaxation and then using Raghavan-Thompson [58] randomized rounding.”
ViNEYard: Virtual Network Embedding Algorithms With Coordinated Node and Link Mapping (2012, unknown): “Techniques of randomized rounding for linear programming relaxations to obtain approximation algorithms was first introduced in [37].”
Clustering Categories in Support Vector Machines (2017, methodology): “The second strategy, the CL randomized rounding (CLRR) Strategy, performs a randomized rounding, [19], to the fractional assignment vector returned by the”
The fused lasso penalty for learning interpretable medical scoring systems (2017, background): “Although randomized rounding is not a recent technique (see [21]), it is a natural way to find discrete solutions efficiently.”
Fast approximation algorithms for fractional packing and covering problems (1991, methodology): “As in [ 151, our algorithms can also be modified to generate integral approximate solutions and thus yield theorems relating the linear and fractional optima along the lines of Raghavan & Thompson [ZZ] and give alternative deterministic algorithms to obtain the results of Raghavan [ 2 11.”
Pseudo-Boolean optimization (2002, methodology): “[5,69,70]), and the above simple rounding procedures are special cases of the “probabilistic rounding” technique based on conditional probabilities, introduced in [37,142,143].”
Experimental analysis of new algorithms for learning ternary classifiers (2015, methodology): “The basic idea to use the probabilistic method to convert an optimal solution of a relaxation of a problem into an approximately optimal solution to the original problem is standard in computer science and operations research [25].”
Large-Scale Learning with Less RAM via Randomization (2013, methodology): “Randomized Rounding Randomized rounding schemes have been widely used in numerical computing and algorithm design (Raghavan & Tompson, 1987).”