Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee

By Alexander A. Ageev, Maxim Sviridenko. Journal of combinatorial optimization, 2004

411 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/a2e025e9bb755d84b4171f34cac013d5a484ff80

How researchers see this paper

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

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Industrial and Manufacturing Engineering

Citations in the corpus

FemtoCaching: Wireless video content delivery through distributed caching helpers (2011, methodology): “that ˚(X) = L(X) 8 X 2 f0;1gjFjjHj . Let L = P f;u P f!e uL f;u(X) and L f;u(X) = minf1; P h2H(u):h6=0 x f;hg. This establishes condition 1 of 9 Theorem 1. Also, the following is true from results in [40]. Lemma 4: g(X) 1 (1 1=d)d L(X) where d= max u jH(u)j 1. Proof: It has been shown in [40] tha”
Submodular Function Maximization (2014, background): “They also show how the continuous solution y can be efficiently rounded to a feasible discrete solution without loss in objective value, using pipage rounding (Ageev and Sviridenko, 2004).”
The Design of Approximation Algorithms (2011, background): “7 for the maximum cut problem with size constraints is due to Ageev and Sviridenko [3, 2].”
Maximizing a Monotone Submodular Function Subject to a Matroid Constraint (2011, methodology): “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.”
Submodularity and Curvature: The Optimal Algorithm (2010, methodology): “X1,X2,...,Xk of size ‘. We work with continuous functions : [0, 1 ]k ! R+, which are associated with discrete functions f : 2X ! R+ in the following way:”
Budget Feasible Mechanisms (2010, background): “grams can, in some cases, achieve the optimal constant approximation ratio [1].”
Improved approximation algorithms for broadcast scheduling (2006, methodology): “Lemma 4.2. Suppose for each block B(p,i) 2 B, we choose the oset (p,i) uniformly at random in [0, 1 ].”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, background): “Constant factor approximation algorithms are known for the problem of maximizing directed cut [1] or hypergraph cut [3] subject to a uniform matroid (i.”
Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract) (2007, methodology): “Ageev and Sviridenko [1] developed an elegant technique for rounding solutions of linear and non-linear programs that they called “pipage rounding”.”
An Improved Approximation for k-Median and Positive Correlation in Budgeted Optimization (2014, background): “2) to NO((1/ ) log(1/ )).”
Optimal approximation for submodular and supermodular optimization with bounded curvature (2013, methodology): “In their approach, the continuous greedy algorithm first maximizes approximately a multilinear extension of the given submodular function and then applies a pipage rounding technique inspired by [1] to obtain an integral solution.”
Optimal approximation for the submodular welfare problem in the value oracle model (2008, methodology): “A very useful tool that we invoke is a rounding technique introduced by Ageev and Sviridenko [1], and adapted for the matroid polytope by Calinescu et al.”
Submodular function maximization via the multilinear relaxation and contention resolution schemes (2011, methodology): “A useful fact here is that the continuous greedy algorithm for monotone submodular functions [48, 7] finds for every b ∈ [0, 1] a point y∗ ∈ bPI such that F (y∗) ≥ (1 − e−b)maxx∈PI F (x).”
Near-Optimal MAP Inference for Determinantal Point Processes (2012, methodology): “Instead, in our experiments we apply pipage rounding [28] and threshold rounding (rounding all coordinates up or down using a single threshold), which are simple and seem to work well in practice.”
From Small-World Networks to Comparison-Based Search (2011, neutral): “(16) in Ageev and Sviridenko [1]):”
FemtoCaching: Wireless Content Delivery Through Distributed Caching Helpers (2013, methodology): “However, this structural similarity allows us to apply the tools developed in [40] in order to obtain a constant factor approximation to problem (3).”
A Unified Continuous Greedy Algorithm for Submodular Maximization (2011, methodology): “This theorem is based on the method of [1].”