Loading...
Please wait, while we are loading the content...
Similar Documents
Using the fglss-reduction to prove inapproximability results for minimum vertex cover in hypergraphs.
| Content Provider | CiteSeerX |
|---|---|
| Author | Goldreich, Oded |
| Abstract | Using known results regarding PCP, we present simple proofs of the inapproximability of vertex cover for hypergraphs. Specifically, we show that 1. Approximating the size of the minimum vertex cover in O(1)-regular hypergraphs to within a factor of 1.99999 is NP-hard. 2. Approximating the size of the minimum vertex cover in 4-regular hypergraphs to within a factor of 1.49999 is NP-hard. Both results are inferior to known results (by Trevisan (2001) and Holmerin (2001)), but they are derived using much simpler proofs. Furthermore, these proofs demonstrate the applicability of the FGLSS-reduction in the context of reductions among combinatorial optimization problems. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Minimum Vertex Cover Prove Inapproximability Result Simple Proof 4-regular Hypergraphs Much Simpler Proof Combinatorial Optimization Problem Regular Hypergraphs Vertex Cover |
| Content Type | Text |
