| Property |
Value |
| dbo:abstract
|
- 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 técnicas 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. Dado un conjunto de elementos (llamado universo) y conjuntos cuya unión comprende el universo, el problema del conjunto de cobertura consiste en identificar el menor número de conjuntos cuya unión aun contiene todos los elementos del universo. Por ejemplo, sea y los conjuntos . Claramente, la unión de todos los conjuntos de contiene todos los elementos de . Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con menor número de elementos: . (es)
- 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 técnicas 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. Dado un conjunto de elementos (llamado universo) y conjuntos cuya unión comprende el universo, el problema del conjunto de cobertura consiste en identificar el menor número de conjuntos cuya unión aun contiene todos los elementos del universo. Por ejemplo, sea y los conjuntos . Claramente, la unión de todos los conjuntos de contiene todos los elementos de . Sin embargo, podemos cubrir todos los elementos con el siguiente conjunto de elementos, con menor número de elementos: . (es)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
| |
| dbo:wikiPageRevisionID
| |
| prop-es:author1Link
|
- Uriel Feige (es)
- Noga Alon (es)
- Carsten Lund (es)
- Ran Raz (es)
- Uriel Feige (es)
- Noga Alon (es)
- Carsten Lund (es)
- Ran Raz (es)
|
| prop-es:author2Link
|
- Shmuel Safra (es)
- Mihalis Yannakakis (es)
- Shmuel Safra (es)
- Mihalis Yannakakis (es)
|
| prop-es:author3Link
|
- Shmuel Safra (es)
- Shmuel Safra (es)
|
| prop-es:authorlink
|
- Ronald L. Rivest (es)
- Thomas H. Cormen (es)
- Charles E. Leiserson (es)
- Clifford Stein (es)
- Vijay Vazirani (es)
- Ronald L. Rivest (es)
- Thomas H. Cormen (es)
- Charles E. Leiserson (es)
- Clifford Stein (es)
- Vijay Vazirani (es)
|
| prop-es:chapter
|
- A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP (es)
- A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP (es)
|
| prop-es:doi
| |
| prop-es:first
|
- Dana (es)
- Noga (es)
- Uriel (es)
- Ran (es)
- Clifford (es)
- Charles E. (es)
- Thomas H. (es)
- Vijay V. (es)
- Carsten (es)
- Ronald L. (es)
- Shmuel (es)
- Mihalis (es)
- Dana (es)
- Noga (es)
- Uriel (es)
- Ran (es)
- Clifford (es)
- Charles E. (es)
- Thomas H. (es)
- Vijay V. (es)
- Carsten (es)
- Ronald L. (es)
- Shmuel (es)
- Mihalis (es)
|
| prop-es:isbn
|
- 0 (xsd:integer)
- 3 (xsd:integer)
- 978 (xsd:integer)
|
| prop-es:issn
|
- 4 (xsd:integer)
- 1549 (xsd:integer)
|
| prop-es:issue
|
- 2 (xsd:integer)
- 4 (xsd:integer)
- 5 (xsd:integer)
|
| prop-es:journal
| |
| prop-es:last
|
- Stein (es)
- Safra (es)
- Feige (es)
- Lund (es)
- Raz (es)
- Cormen (es)
- Vazirani (es)
- Alon (es)
- Leiserson (es)
- Rivest (es)
- Moshkovitz (es)
- Yannakakis (es)
- Stein (es)
- Safra (es)
- Feige (es)
- Lund (es)
- Raz (es)
- Cormen (es)
- Vazirani (es)
- Alon (es)
- Leiserson (es)
- Rivest (es)
- Moshkovitz (es)
- Yannakakis (es)
|
| prop-es:location
|
- Cambridge, Mass. (es)
- Cambridge, Mass. (es)
|
| prop-es:pages
|
- 153 (xsd:integer)
- 475 (xsd:integer)
- 634 (xsd:integer)
- 960 (xsd:integer)
- 1033 (xsd:integer)
|
| prop-es:publisher
|
- Springer-Verlag (es)
- ACM (es)
- MIT Press and McGraw-Hill (es)
- Springer-Verlag (es)
- ACM (es)
- MIT Press and McGraw-Hill (es)
|
| prop-es:title
|
- Introduction to Algorithms (es)
- Approximation Algorithms (es)
- On the hardness of approximating minimization problems (es)
- A threshold of ln n for approximating set cover (es)
- Algorithmic construction of sets for k-restrictions (es)
- STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (es)
- Introduction to Algorithms (es)
- Approximation Algorithms (es)
- On the hardness of approximating minimization problems (es)
- A threshold of ln n for approximating set cover (es)
- Algorithmic construction of sets for k-restrictions (es)
- STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing (es)
|
| prop-es:volume
|
- 2 (xsd:integer)
- 41 (xsd:integer)
- 45 (xsd:integer)
|
| prop-es:year
|
- 1994 (xsd:integer)
- 1997 (xsd:integer)
- 1998 (xsd:integer)
- 2001 (xsd:integer)
- 2006 (xsd:integer)
|
| dct:subject
| |
| 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 técnicas 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)
- 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 técnicas 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)
|
| rdfs:label
|
- Problema del conjunto de cobertura (es)
- Problema del conjunto de cobertura (es)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is owl:sameAs
of | |
| is foaf:primaryTopic
of | |
