El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional. Es un problema que ha llevado al desarrollo de tecnicas fundamentales para el campo de los algoritmos de aproximación. También es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972.

Author1-Link
  • Carsten Lund (es)
  • Noga Alon (es)
  • Ran Raz (es)
  • Uriel Feige (es)
Author2-Link
  • Mihalis Yannakakis (es)
  • Shmuel Safra (es)
Author3-Link
  • Shmuel Safra (es)
Authorlink
  • Charles E. Leiserson (es)
  • Clifford Stein (es)
  • Ronald L. Rivest (es)
  • Thomas H. Cormen (es)
  • Vijay Vazirani (es)
Chapter
  • A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP (es)
rdfs:comment
  • El problema del Set Covering, también conocido por sus siglas SCP es un problema clásico en combinatoria, ciencias de la computación y teoría de la complejidad computacional. Es un problema que ha llevado al desarrollo de tecnicas fundamentales para el campo de los algoritmos de aproximación. También es uno de los problemas de la Lista de 21 problemas NP-completos de Karp cuya NP-completitud fue demostrada en 1972. (es)
Doi
  • 101145 (xsd:integer)
First [12 values]
foaf:isPrimaryTopicOf
Isbn
  • 0 (xsd:integer)
  • 3 (xsd:integer)
  • 978 (xsd:integer)
Issn
  • 1549 (xsd:integer)
  • 4 (xsd:integer)
Issue
  • 2 (xsd:integer)
  • 4 (xsd:integer)
  • 5 (xsd:integer)
Journal
rdfs:label
  • Problema del conjunto de cobertura (es)
Last [12 values]
Location
  • Cambridge, Mass. (es)
Pages
  • 1033 (xsd:integer)
  • 153 (xsd:integer)
  • 475 (xsd:integer)
  • 634 (xsd:integer)
  • 960 (xsd:integer)
Is foaf:primaryTopic of
Publisher
  • ACM (es)
  • MIT Press and McGraw-Hill (es)
  • Springer-Verlag (es)
dcterms:subject
Title
  • A threshold of ln n for approximating set cover (es)
  • Algorithmic construction of sets for k-restrictions (es)
  • Approximation Algorithms (es)
  • Introduction to Algorithms (es)
  • On the hardness of approximating minimization problems (es)
  • STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (es)
Volume
  • 2 (xsd:integer)
  • 41 (xsd:integer)
  • 45 (xsd:integer)
prov:wasDerivedFrom
dbpedia-owl:wikiPageID
  • 2112051 (xsd:integer)
dbpedia-owl:wikiPageLength
  • 10395 (xsd:integer)
dbpedia-owl:wikiPageOutDegree
  • 21 (xsd:integer)
Is dbpedia-owl:wikiPageRedirects of
dbpedia-owl:wikiPageRevisionID
  • 75974625 (xsd:integer)
prop-latam:wikiPageUsesTemplate
dbpedia-owl:wikiPageWikiLink [19 values]
Is dbpedia-owl:wikiPageWikiLink of
Year
  • 1994 (xsd:integer)
  • 1997 (xsd:integer)
  • 1998 (xsd:integer)
  • 2001 (xsd:integer)
  • 2006 (xsd:integer)