A note on unique games
type: Item
instance of: scholarly article
title: A note on unique games
zbMATH Open document ID: 1185.91017
author: Adi Avidor
author: Ricky Rosen
published in: Information Processing Letters
publication date: 2010-01-29T00:00:00Z
Mathematics Subject Classification ID: 91A05
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5664463
zbMATH Keywords: algorithms
zbMATH Keywords: analysis of algorithms
zbMATH Keywords: approximation algorithms
zbMATH Keywords: computational complexity
zbMATH Keywords: theory of computation
MaRDI profile type: Publication
full work available at URL: j.ipl.2006.03.004
OpenAlex ID: W2081469573
cites work: Proof verification and the hardness of approximation problems
cites work: Q4230321
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: On the hardness of approximating Multicut and Sparsest-Cut
cites work: Conditional hardness for approximate coloring
cites work: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Hardness of Approximate Hypergraph Coloring
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Some optimal inapproximability results
cites work: On the power of unique 2-prover 1-round games
cites work: A PCP characterization of NP with optimal amortized query complexity
DOI: 10.1016/J.IPL.2006.03.004
description: scientific article; zbMATH DE number 5664463