Hardness of Set Cover with Intersection 1

Volume: 1853, Pages: 624 - 635
Published: Jul 9, 2000
Abstract
We consider a restricted version of the general Set Covering problem in which each set in the given set system intersects with any other set in at most 1 element. We show that the Set Covering problem with intersection 1 cannot be approximated within a o(log n) factor in random polynomial time unless N P ⊆ ZTIME(nO(log log n)). We also observe that the main challenge in derandomizing this reduction lies in finding a hitting set for large volume...
Paper Details
Title
Hardness of Set Cover with Intersection 1
Published Date
Jul 9, 2000
Volume
1853
Pages
624 - 635
Citation AnalysisPro
  • Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
  • Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.