Please note that eDoc will be permanently shut down in the first quarter of 2021!      Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents



  history
ID: 518142.0, MPI für Informatik / Algorithms and Complexity Group
Hardness of Set Cover with Intersection 1
Authors:Kumar, V. S. Anil; Arya, Sunil; Hariharan, Ramesh
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Automata, Languages and Programming, Proceedings of the 27th International Colloquium (ICALP-00)
Start Page:624
End Page:635
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Geneva, Switzerland
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2000-07-09
End Date of Conference/Meeting 
 (YYYY-MM-DD):
2000-07-15
Review Status:not specified
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-93D64C1F0FB48843C1256A0000527E39-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.