Near-optimal algorithms for unique games
From MaRDI portal
Publication:2931385
DOI10.1145/1132516.1132547zbMATH Open1301.68267OpenAlexW2165732281MaRDI QIDQ2931385FDOQ2931385
Authors: Konstantin Makarychev, Yury 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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Approximation algorithms (68W25)
Cited In (35)
- Approximating CSPs Using LP Relaxation
- Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs
- Making the Long Code Shorter
- An improved heuristic for the ``Ulam-Rényi game
- Approximating maximum satisfiable subsystems of linear equations of bounded width
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Column subset selection problem is UG-hard
- Lasserre integrality gaps for graph spanners and related problems
- Title not available (Why is that?)
- A note on unique games
- On Khot’s unique games conjecture
- Title not available (Why is that?)
- Approximate Lasserre integrality gap for unique games
- Approximation Algorithms for CSPs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Mathematics of computation through the lens of linear equations and lattices
- Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
- Approximating Unique Games Using Low Diameter Graph Decomposition
- Angular synchronization by eigenvectors and semidefinite programming
- Sharp kernel clustering algorithms and their associated Grothendieck inequalities
- Spectral algorithms for unique games
- Approximate kernel clustering
- Hard constraint satisfaction problems have hard gaps at location 1
- Approximation algorithms for unique games
- Playing Games with Approximation Algorithms
- Large violation of Bell inequalities with low entanglement
- Improved Rounding for Parallel Repeated Unique Games
- Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
- Title not available (Why is that?)
- Contention resolution, matrix scaling and fair allocation
- Robustly solvable constraint satisfaction problems
- Unique games on expanding constraint graphs are easy (extended abstract)
- Non-unique games over compact groups and orientation estimation in cryo-EM
- Title not available (Why is that?)
This page was built for publication: Near-optimal algorithms for unique games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2931385)
