de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Hardness of Set Cover with Intersection 1

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44863

Kumar,  V. S. Anil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44034

Arya,  Sunil
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44586

Hariharan,  Ramesh
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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 (Eds.), 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.