Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
type: Item
instance of: scholarly article
title: Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
zbMATH Open document ID: 1343.68094
DOI: 10.1007/978-3-642-22670-0_11
author: Oded Goldreich
published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
publication date: 2011-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 5940579
zbMATH Keywords: complexity of approximation
zbMATH Keywords: combinatorial optimization problems
zbMATH Keywords: vertex cover
zbMATH Keywords: PCP
zbMATH Keywords: regular hypergraphs
MaRDI profile type: Publication
full work available at URL: 978-3-642-22670-0 11
OpenAlex ID: W1572712645
cites work: Proof verification and the hardness of approximation problems
cites work: Probabilistic checking of proofs
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
cites work: The importance of being biased
cites work: Interactive proofs and the hardness of approximating cliques
cites work: Modern cryptography, probabilistic proofs and pseudo-randomness
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: The hardness of approximation: Gap location
cites work: Non-approximability results for optimization problems on bounded degree instances
Recommended article: On approximation of the vertex cover problem in hypergraphs
Recommended article: Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
Recommended article: Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
Recommended article: Q4737227
Recommended article: An approximation algorithm for the partial vertex cover problem in hypergraphs
Recommended article: On the hardness of approximating minimum vertex cover
Recommended article: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs
Recommended article: Q3688431
Recommended article: Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
Recommended article: Q4952635
description: scientific article