Near-optimal algorithms for unique games
From MaRDI portal
Publication:2931385
DOI10.1145/1132516.1132547zbMath1301.68267OpenAlexW2165732281MaRDI QIDQ2931385
Yury Makarychev, Konstantin Makarychev, Moses Charikar
Publication date: 25 November 2014
Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1132516.1132547
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Approximation algorithms (68W25)
Related Items
Hard constraint satisfaction problems have hard gaps at location 1, Approximating CSPs Using LP Relaxation, Making the Long Code Shorter, Column subset selection problem is UG-hard, Angular synchronization by eigenvectors and semidefinite programming, Unnamed Item, Mathematics of computation through the lens of linear equations and lattices, Spectral algorithms for unique games, Unnamed Item, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Approximation Algorithms for CSPs, Approximating Unique Games Using Low Diameter Graph Decomposition, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Approximating maximum satisfiable subsystems of linear equations of bounded width, Sharp kernel clustering algorithms and their associated Grothendieck inequalities, Large violation of Bell inequalities with low entanglement, Unnamed Item, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, Robustly Solvable Constraint Satisfaction Problems, Approximate Kernel Clustering, On Khot’s unique games conjecture, Non-unique games over compact groups and orientation estimation in cryo-EM, Contention resolution, matrix scaling and fair allocation, Unnamed Item, Lasserre integrality gaps for graph spanners and related problems
