Fast SDP algorithms for constraint satisfaction problems

MaRDI QIDQ5417659zbMATH OpenFDO

Authors David Steurer

Publication date 22 May 2014

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• scientific article; zbMATH DE number 6381632
• Near-optimal algorithms for maximum constraint satisfaction problems
• Near-optimal algorithms for unique games
• An LP-Designed Algorithm for Constraint Satisfaction
• Approximation of non-Boolean 2CSP

Cited in

(13)

• Correlation clustering in data streams
• Fast and parallel decomposition of constraint satisfaction problems
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction
• Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
• Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems
• Rounding sum-of-squares relaxations
• Subsampling mathematical relaxations and average-case complexity
• Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP
• An LP-Designed Algorithm for Constraint Satisfaction
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• Riemannian Langevin algorithm for solving semidefinite programs
• Triangles improve 0.878 approximation for Maxcut

This page was built for publication: Fast SDP algorithms for constraint satisfaction problems

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