# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Hardness of Set Cover with Intersection 1

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Kumar, V. S. A., Arya, S., & Hariharan, R. (2000). Hardness of Set Cover with Intersection
1. In U. Montanari, J. D. P. Rolim, & E. Welzl (*Automata,
Languages and Programming, Proceedings of the 27th International Colloquium (ICALP-00)* (pp. 624-635). Berlin, Germany:
Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-33B7-F

##### 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 s
et
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
$NP \subseteq ZTIME(n^{O(\log\log n)})$.
We also observe that the main challenge in
derandomizing this reduction lies in find a hitting set for large
volume combinatorial rectangles satisfying certain intersection
properties. These properties are not satisfied by current methods
of hitting set construction.