Publication:3002828

DOI10.4086/toc.2011.v007a003zbMath1243.68183MaRDI QIDQ3002828

Per Austrin, Shmuel Safra, Subhash A. Khot

Publication date: 24 May 2011

Published in: Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.4086/toc.2011.v007a003

zbMATH Keywords

approximation; independent set; hardness; vertex cover; unique games conjecture; bounded degree

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

On the Lovász Theta Function for Independent Sets in Sparse Graphs, On Constant Time Approximation of Parameters of Bounded Degree Graphs, Multitasking Capacity: Hardness Results and Improved Constructions, Inapproximability of $H$-Transversal/Packing, Unnamed Item, Complexity of approximating CSP with balance/hard constraints, Combinatorial optimization. Abstracts from the workshop held November 9--15, 2014., New techniques for approximating optimal substructure problems in power-law graphs, Secluded connectivity problems, Complexity and lowers bounds for power edge set problem, Affine reductions for LPs and SDPs, A note on degree vs gap of Min-Rep label cover and improved inapproximability for connectivity problems, Donation center location problem, Approximation algorithms for vertex happiness, Competitive and collaborative influence in social networks, Locally Stable Marriage with Strict Preferences, Maximum Weighted Independent Sets with a Budget, Recoverable Values for Independent Sets, Vertex Cover in Graphs with Locally Few Colors, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses