MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kumar, V. S. Anil
Arya, Sunil
Ramesh, Hariharan		dblp
dblp
dblp
Editor(s):
Montanari, Ugo
Rolim, José D. P.
Welzl, Emo		dblp
dblp
dblp
BibTeX cite key*:
Kumar2000
Title, Booktitle
Title*:
Hardness of Set Cover with Intersection 1
Booktitle*:
Automata, Languages and Programming, Proceedings of the 27th International Colloquium (ICALP-00)
Event, URLs
Conference URL::
http://www.informatik.uni-trier.de/~ley/db/conf/icalp/index.html
Downloading URL:
Event Address*:
Geneva, Switzerland
Language:
English
Event Date*
(no longer used):
July 9-15, 2000
Organization:
EATCS
Event Start Date:
9 July 2000
Event End Date:
15 July 2000
Publisher
Name*:
Springer
URL:
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1853
Number:
Month:
Pages:
624-635
Year*:
2000
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Kumar2000,
AUTHOR = {Kumar, V. S. Anil and Arya, Sunil and Ramesh, Hariharan},
 EDITOR = {Montanari, Ugo and Rolim, Jos{\'e} D. P. and Welzl, Emo},
 TITLE = {Hardness of Set Cover with Intersection 1},
 BOOKTITLE = {Automata, Languages and Programming, Proceedings of the 27th International Colloquium (ICALP-00)},
 PUBLISHER = {Springer},
 YEAR = {2000},
 ORGANIZATION = {EATCS},
 VOLUME = {1853},
 PAGES = {624--635},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Geneva, Switzerland},
}

Entry last modified by Christine Kiesel, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
V.S.Anil Kumar		Created
02/27/2001 16:01:02
Revisions
6.
5.
4.
3.
2.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Anja Becker
Anja Becker		Edit Dates
30.05.2005 15:27:49
30.05.2005 15:27:16
30.05.2005 15:27:14
20.03.2001 17:03:30
15.03.2001 10:57:34