A note on unique games

DOI10.1016/J.IPL.2006.03.004zbMATH Open1185.91017OpenAlexW2081469573MaRDI QIDQ845686FDOQ845686

Authors: Adi Avidor, Ricky Rosen 

Publication date: 29 January 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.03.004

Recommendations

• Approximation algorithms for unique games
• Near-optimal algorithms for unique games
• Unique games on expanding constraint graphs are easy (extended abstract)
• A new point of NP-hardness for unique games
• Spectral algorithms for unique games

zbMATH Keywords

algorithmscomputational complexityanalysis of algorithmsapproximation algorithmstheory of computation

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05)

Cites Work

• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Proof verification and the hardness of approximation problems
• Some optimal inapproximability results
• On the hardness of approximating Multicut and Sparsest-Cut
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A PCP characterization of NP with optimal amortized query complexity
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Title not available (Why is that?)
• Conditional hardness for approximate coloring
• Hardness of Approximate Hypergraph Coloring
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

Cited In (4)

• A note on bus games
• On unique games with negative weights
• Approximation algorithms for unique games
• How to Play Unique Games on Expanders

This page was built for publication: A note on unique games

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