son disjuntos 2 a 2, y el tamaño del empaquetamiento es
El problema es claramente un problema NP debido a que, dadok subconjuntos, podemos fácilmente verificar que ellos son disjuntos 2 a 2 en tiempo polinomial.
Usted está, en resumen, buscando un empaquetamiento de conjuntos (
Como otro ejemplo, supongamos que usted está en una convención de embajadores foráneos, cada uno de los cuales habla inglés y también otros idiomas.
Por otra parte, usted también quiere entregar su anuncio a tantos embajadores como sea posible.
En este caso, los elementos del conjunto son idiomas distintos del inglés, y los subconjuntos son los conjuntos de idiomas hablados por un embajador en particular.
Un empaquetamiento máximo escogerá el número más grande posible de embajadores bajo la restricción deseada.
Aunque el problema es difícil de resolver en general, en este ejemplo una buena heurística es escoger a embajadores que solo hablen lenguajes no tan comunes primero, con el fin de que muchos otros no queden descalificados.
Esto parece hacer que el problema sea difícil, pero la mayoría de los resultados que se aplican al problema sin tomar en cuenta los pesos se pueden aplicar al problema con pesos también.
El problema de empaquetamiento de conjuntos puede resultar difícil para algún k, pero no es difícil encontrar un k para el cual el problema es fácil con una entrada en particular.
Continuaremos haciendo esto hasta que no quede ningún conjunto por revisar, y tengamos un empaquetamiento de conjuntos de algún tamaño, aunque esto no garantiza obtener un empaquetamiento de conjuntos máximo.
Aunque ningún algoritmo puede siempre dar resultados cerca del máximo (ver la sección que sigue), para muchas entradas en la práctica el algoritmo funciona bien.
[2] El mejor algoritmo conocido hasta ahora lo aproxima en un factor de
Sin embargo, el problema tiene una variante que es mucho más tratable: si asumimos que ningún subconjunto tiene k≥3 elementos, La respuesta puede ser aproximada dentro de un factor de k/2 + ε para todo ε > 0; en particular, el problema con conjuntos de tamaño 3 puede ser aproximado alrededor del 50 %.
Existe una reducción uno a uno en tiempo polinomial entre el problema conjunto independiente y el problema de empaquetamiento de conjuntos: Esta es una aplicación bidireccional, y muestra que los 2 problemas son igualmente difíciles de aproximar.
Un emparejamiento máximo puede ser encontrado en tiempo polinomial, pero encontrar el emparejamiento 3-dimensional más grande o el conjunto independiente más grande es un problema NP-duro.
El empaquetamiento máximo no necesita cubrir a cada elemento posible.
Encontrar tal cubrimiento exacto, sin importar el tamaño, es un problema NP-completo.
Karp originalmente mostró que el problema del empaquetamiento de conjuntos era NP-completo a través de una reducción basada en el problema del clique.