A note on unique games
From MaRDI portal
Publication:845686
DOI10.1016/j.ipl.2006.03.004zbMath1185.91017OpenAlexW2081469573MaRDI QIDQ845686
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
2-person games (91A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- On the hardness of approximating Multicut and Sparsest-Cut
- Conditional hardness for approximate coloring
- Hardness of Approximate Hypergraph Coloring
- Proof verification and the hardness of approximation problems
- A PCP characterization of NP with optimal amortized query complexity
- On the power of unique 2-prover 1-round games
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Some optimal inapproximability results
