Approximating vertex cover in dense hypergraphs (Q450531): Difference between revisions

@@ Property / arXiv ID @@
+.2573
@@ Property / arXiv ID: 1012.2573 / rank @@
+Normal rank
@@ Property / cites work @@
+On a theorem of Lovász on covers in \(r\)-partite hypergraphs
+Normal rank
@@ Property / cites work @@
+Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
+Normal rank
@@ Property / cites work @@
+Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
+Normal rank
@@ Property / cites work @@
+Approximating the dense set-cover problem
@@ Property / cites work: Approximating the dense set-cover problem / rank @@
+Normal rank
@@ Property / cites work @@
+Improved non-approximability results for minimum vertex cover with density constraints
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
+Normal rank
@@ Property / cites work @@
+Q4737227
@@ Property / cites work: Q4737227 / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
+Normal rank
@@ Property / cites work @@
+Q2921716
@@ Property / cites work: Q2921716 / rank @@
+Normal rank
@@ Property / cites work @@
+A better approximation ratio for the vertex cover problem
+Normal rank
@@ Property / cites work @@
+Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
+Normal rank
@@ Property / cites work @@
+The Complexity of Perfect Matching Problems on Dense Hypergraphs
+Normal rank
@@ Property / cites work @@
+Q4395327
@@ Property / cites work: Q4395327 / rank @@
+Normal rank
@@ Property / cites work @@
+On the power of unique 2-prover 1-round games
@@ Property / cites work: On the power of unique 2-prover 1-round games / rank @@
+Normal rank
@@ Property / cites work @@
+Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
+Normal rank
@@ Property / cites work @@
+Approximate Set Covering in Uniform Hypergraphs
@@ Property / cites work: Approximate Set Covering in Uniform Hypergraphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4180391
@@ Property / cites work: Q4180391 / rank @@
+Normal rank
@@ Property / cites work @@
+On approximation of the vertex cover problem in hypergraphs
+Normal rank
@@ Property / cites work @@
+Non-approximability results for optimization problems on bounded degree instances
+Normal rank