Home News About Us Contact Contributors Disclaimer 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:


          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.