Problema de la división de un conjunto

De Wikipedia, la enciclopedia libre

En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una partición de S en dos subconjuntos S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? Este problema es NP-completo.[1]​

Visto como un problema de optimización, se llama el problema de división del máximo conjunto (en inglés Max Set Splitting) y consiste en encontrar la partición que maximiza el número de elementos divididos de F. Este es un problema APX[2]​ (y NP-hard). El problema sigue siendo NP-hard incluso si todos los subconjuntos de F contienen el mismo número de elementos, todos ellos mayores que 1.[3]​

Como problema de decisión, el Max Set Splitting, también llamado "Set Splitting" queda como sigue: dado un número entero k, ¿existe una partición de S que divida al menos k subconjuntos de F? Si k toma el valor de un parámetro dado, luego el "Set Splitting" posee complejidad parametrizada, es decir existe un algoritmo polinómico para cualquier valor de k.[3]​

Referencias[editar]

  1. ↑ Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Nueva York: W.H. Freeman. ISBN 0-7167-1045-5. 
  2. ↑ E. Petrank, "The hardness of approximation: Gap location", Computational Complexity, 4(1994), 133–157.
  3. ↑ a b "An FPT Algorithm for Set Splitting"
Obtenido de «https://es.wikipedia.org/w/index.php?title=Problema_de_la_división_de_un_conjunto&oldid=119639189»