A note on unique games
From MaRDI portal
Publication:845686
DOI10.1016/J.IPL.2006.03.004zbMATH Open1185.91017OpenAlexW2081469573MaRDI QIDQ845686FDOQ845686
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
algorithmscomputational complexityanalysis of algorithmsapproximation algorithmstheory of computation
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 2-person games (91A05)
Cites Work
- Title not available (Why is that?)
- 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
- Conditional hardness for approximate coloring
- Hardness of Approximate Hypergraph Coloring
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Cited In (2)
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)
