Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs (Q3088105): Difference between revisions

@@ Property / arXiv ID @@
+.4175
@@ Property / arXiv ID: 1105.4175 / rank @@
+Normal rank
@@ Property / cites work @@
+On a theorem of Lovász on covers in \(r\)-partite hypergraphs
+Normal rank
@@ Property / cites work @@
+Uniformly cross intersecting families
@@ Property / cites work: Uniformly cross intersecting families / rank @@
+Normal rank
@@ Property / cites work @@
+Proof verification and the hardness of approximation problems
+Normal rank
@@ Property / cites work @@
+Probabilistic checking of proofs
@@ Property / cites work: Probabilistic checking of proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3002828
@@ Property / cites work: Q3002828 / rank @@
+Normal rank
@@ Property / cites work @@
+Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimum vertex cover
+Normal rank
@@ Property / cites work @@
+Schema mapping discovery from data instances
@@ Property / cites work: Schema mapping discovery from data instances / rank @@
+Normal rank
@@ Property / cites work @@
+Q4860774
@@ Property / cites work: Q4860774 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
+Normal rank
@@ Property / cites work @@
+Combinatorial Pattern Matching
@@ Property / cites work: Combinatorial Pattern Matching / rank @@
+Normal rank
@@ Property / cites work @@
+Automata, Languages and Programming
@@ Property / cites work: Automata, Languages and Programming / 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 @@
+Q5365139
@@ Property / cites work: Q5365139 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4180391
@@ Property / cites work: Q4180391 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549708
@@ Property / cites work: Q3549708 / rank @@
+Normal rank
@@ Property / cites work @@
+A Parallel Repetition Theorem
@@ Property / cites work: A Parallel Repetition Theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Non-approximability results for optimization problems on bounded degree instances
+Normal rank