Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
 
 
DownloadE-Mail
 Lokale TagsFreigabegeschichteDetailsÜbersicht
  Hardness of Set Cover with Intersection 1

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.

Item is

 

einblenden: alle ausblenden: alle

Basisdaten

einblenden: ausblenden:
Datensatz-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33B7-F Versions-Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33B9-B
Genre: Konferenzbeitrag

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Kumar, V. S. Anil1, Autor           
Arya, Sunil1, Autor           
Hariharan, Ramesh1, Autor           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2010-03-022000
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 518142
Anderer: Local-ID: C1256428004B93B8-93D64C1F0FB48843C1256A0000527E39-Kumar2000
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Geneva, Switzerland
Start-/Enddatum: 2000-07-09 - 2000-07-15

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: Automata, Languages and Programming, Proceedings of the 27th International Colloquium (ICALP-00)
Genre der Quelle: Konferenzband
 Urheber:
Montanari, Ugo, Herausgeber
Rolim, José D. P., Herausgeber
Welzl, Emo, Herausgeber
Affiliations:
-
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 624 - 635 Identifikator: -

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 1853 Artikelnummer: - Start- / Endseite: - Identifikator: -