A note on unique games

DOI10.1016/J.IPL.2006.03.004MaRDI QIDQ845686zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

Cited in

(7)

• Unique games on the hypercube
• A new point of NP-hardness for unique games
• A note on bus games
• How to Play Unique Games on Expanders
• Candidate hard unique game
• Approximation algorithms for unique games
• On unique games with negative weights

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)