Approximating unique games
From MaRDI portal
Publication:3581527
DOI10.1145/1109557.1109569zbMath1192.91012OpenAlexW4233786017MaRDI QIDQ3581527
Publication date: 16 August 2010
Published in: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1109557.1109569
Games involving graphs (91A43) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04)
Related Items
Making the Long Code Shorter ⋮ Column subset selection problem is UG-hard ⋮ FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs ⋮ Spectral algorithms for unique games ⋮ FPT algorithms for path-transversal and cycle-transversal problems ⋮ Graph Clustering using Effective Resistance ⋮ 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 ⋮ Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
