Approximating unique games

DOI10.1145/1109557.1109569MaRDI QIDQ3581527zbMATH OpenOpenAlexFDO

Authors Anupam Gupta, Kunal Talwar

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

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) Games involving graphs (91A43)

Cited in

(11)

• Making the Long Code Shorter
• Approximating maximum satisfiable subsystems of linear equations of bounded width
• Approximating unique games using low diameter graph decomposition
• FPT algorithms for path-transversal and cycle-transversal problems
• Column subset selection problem is UG-hard
• Graph Clustering using Effective Resistance
• Approximation Algorithms for CSPs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Spectral algorithms for unique games
• FPT Algorithms for Path-Transversals and Cycle-Transversals Problems in Graphs
• Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem

This page was built for publication: Approximating unique games

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