Encontrar juegos que no se intersecan. Algoritmo de aproximación

Question

Estoy tratando de resolver el siguiente problema. Deje $S$ a un y $F \subset {S \choose k}$ $F$ es un subconjunto del conjunto de todos los $k$-conjuntos de $S$.

Un conjunto $M \subset F$ de manera tal que no hay dos elementos de $M$ se cruzan se llama una solución para el problema.

Estoy buscando un algoritmo de $A$ que encuentre una solución para el problema anterior de tal forma que si la solución dada es un conjunto $M$ y el mayor conjunto que es una solución para la misma instancia es $M^*$

$$\frac{|M|}{|M^*|} \geq \frac1{k}\qquad (1) $$

El único algoritmo que pueda ver por el problema anterior es elegir un elemento $P$$F$, eliminar todos los elementos en $F$ que se cruzan con $P$ y continuar.

Sin embargo, yo no soy capaz de analizar el procedimiento anterior para obtener el dado obligado (si aún alcanzable).

Consejos sobre este problema?

Answer 1

Este problema normalmente se denomina la ponderado conjunto de problemas de embalaje. Como nota al margen, este problema es NP-completo; de hecho, cuando llegué a conocer, solo por hoy (gracias, OP!), es uno de Karp de la pandilla de 21!

He aquí una sencilla prueba de que la heurística que se describe en la pregunta da un conjunto de $M$ que es a lo más un factor de $k$ a partir de la óptima, llame a esta $M^*$. Crear un gráfico bipartito con la pone en $M$ como la izquierda vértices, y la pone en $M^*$ como el derecho de los vértices. Agregar un borde entre el $A \in M$ $B \in M^*$ fib $A$ intersecta $B$. Aquí están algunas observaciones básicas:

• Cada vértice derecho tiene al menos un vecino de la izquierda. De lo contrario, podríamos añadir a este conjunto de forma segura a $M$ para obtener una familia más grande, contradiciendo la maximality de $M$.
• Cada vértice izquierdo tiene en la mayoría de las $k$ derecho vecinos. De lo contrario, dos de los derecho de los vecinos se ven obligados a "compartir" un elemento común, que contradice la suposición de que $M^*$ es la desunión de la familia de conjuntos.

Poner a estos dos juntos, usted debería ser capaz de deducir que $|M^*| \leq |M|/k$. (Tenga en cuenta que no tenemos la desigualdad estricta.) Por cierto, el conjunto de problemas de embalaje para el caso de $k=2$ es la conocida máxima problema de coincidencia. Si usted ha visto matchings antes, os animo a trabajar a cabo la prueba para este caso específico, es muy esclarecedor.

Este límite ajustado, como se ve en el siguiente ejemplo: supongamos $S$ el conjunto de $k^2$ puntos dispuestos como una $k \times k$ cuadrícula. Definir $M$ a ser la columna de la izquierda. Definir $M^*$ ser parte de la familia de $k$ filas, cada una de las cuales contiene $k$ puntos. Tome $F$$M \cup M^*$. Claramente $|M| =1$$|M^*|=k$.

Mejor heurística. Al parecer, el mejor local de la heurística la heurística son conocidos por este problema, logrando un factor de $k/2+\epsilon$ aproximación. Véase por ejemplo: "la Aproximación Discreta de las Colecciones a través de las Mejoras Locales" por Halldorsson.

Answer 2

¿Qué ocurre con el particionado $S$ $k$ juegos separados de elemento?