The RPR2 rounding technique for semidefinite programs

DOI10.1016/J.JALGOR.2004.11.003MaRDI QIDQ5483509zbMATH OpenOpenAlexFDO

Authors Michael Langberg, Uriel Feige

Publication date 14 August 2006

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jalgor.2004.11.003

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Semidefinite programming (90C22)

Recommendations

• scientific article; zbMATH DE number 1754595
• A rounding procedure for semidefinite optimization
• Rounding of convex sets and efficient gradient methods for linear programming problems
• scientific article; zbMATH DE number 5847045
• Rounding-based heuristics for nonconvex MINLPS
• Certified roundoff error bounds using semidefinite programming
• scientific article; zbMATH DE number 2081093
• Primal-Dual Interior-Point Methods for Semidefinite Programming in Finite Precision
• A simplified treatment of Ramana's exact dual for semidefinite programming

Cited in

(29)

• The MIN-cut and vertex separator problem
• On bisections of graphs without complete bipartite graphs
• An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
• On judicious bisections of graphs
• Bisections of graphs without \(K_{2, l}\)
• Bisections of graphs
• Approximation algorithms for MAX RES CUT with limited unbalanced constraints
• An improved kernel for max-bisection above tight lower bound
• How much data is sufficient to learn high-performing algorithms?
• Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
• Graph partitioning: an updated survey
• On the mysteries of MAX NAE-SAT
• Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix
• An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
• A rounding procedure for semidefinite optimization
• scientific article; zbMATH DE number 1754595 (Why is no real title available?)
• 10 problems for partitions of triangle-free graphs
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems
• A semidefinite programming approach to side chain positioning with new rounding strategies
• An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding
• A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• On the NP-hardness approximation curve for Max-2Lin(2)
• Improved approximation algorithms for the max-bisection and the disjoint 2-catalog segmentation problems
• Rounding sum-of-squares relaxations
• An improved approximation algorithm for hypergraph max p-section
• Sherali-Adams strikes back

This page was built for publication: The RPR2 rounding technique for semidefinite programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5483509)