Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs (Q491613): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W1986334373
@@ Property / OpenAlex ID: W1986334373 / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.2000
@@ Property / arXiv ID: 1107.2000 / 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 @@
+Approximating Subdense Instances of Covering Problems
+Normal rank
@@ Property / cites work @@
+Approximating vertex cover in dense hypergraphs
@@ Property / cites work: Approximating vertex cover in dense hypergraphs / 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 @@
+Q2921716
@@ Property / cites work: Q2921716 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Computational Complexity of Combinatorial Problems
+Normal rank
@@ Property / cites work @@
+Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
+Normal rank
@@ Property / cites work @@
+COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
+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 @@
+Q5365139
@@ Property / cites work: Q5365139 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4180391
@@ Property / cites work: Q4180391 / rank @@
+Normal rank
@@ Property / cites work @@
+Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
+Normal rank
@@ Property / cites work @@
+Non-approximability results for optimization problems on bounded degree instances
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:491613