English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
Add to Basket
 Local TagsRelease HistoryDetailsSummary
  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

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33B7-F Version Permalink: https://hdl.handle.net/11858/00-001M-0000-000F-33B9-B
Genre: Conference Paper

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kumar, V. S. Anil1, Author           
Arya, Sunil1, Author           
Hariharan, Ramesh1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022000
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518142
Other: Local-ID: C1256428004B93B8-93D64C1F0FB48843C1256A0000527E39-Kumar2000
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Geneva, Switzerland
Start-/End Date: 2000-07-09 - 2000-07-15

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, Languages and Programming, Proceedings of the 27th International Colloquium (ICALP-00)
Source Genre: Proceedings
 Creator(s):
Montanari, Ugo, Editor
Rolim, José D. P., Editor
Welzl, Emo, Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 624 - 635 Identifier: -

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 1853 Sequence Number: - Start / End Page: - Identifier: -