Restricted parameter range promise set cover problems are easy (Q2258109): Difference between revisions

@@ Property / arXiv ID @@
+.1896
@@ Property / arXiv ID: 1110.1896 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4542515
@@ Property / cites work: Q4542515 / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of approximate optima in lattices, codes, and systems of linear equations
+Normal rank
@@ Property / cites work @@
+Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+Approximating CVP to within almost-polynomial factors is NP-hard
+Normal rank
@@ Property / cites work @@
+Hardness of approximating the minimum distance of a linear code
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+Q3549646
@@ Property / cites work: Q3549646 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation Algorithms for the Set Covering and Vertex Cover Problems
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Hardness of approximating the shortest vector problem in lattices
+Normal rank
@@ Property / cites work @@
+On the ratio of optimal integral and fractional covers
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimization problems
+Normal rank
@@ Property / cites work @@
+The Shortest Vector in a Lattice is Hard to Approximate to within Some Constant
+Normal rank
@@ Property / cites work @@
+Q4829810
@@ Property / cites work: Q4829810 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+Normal rank
@@ Property / cites work @@
+Non-approximability results for optimization problems on bounded degree instances
+Normal rank