de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Hardness of Set Cover with Intersection 1

MPG-Autoren
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;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-000F-33B7-F
Zusammenfassung
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.