Conjunto disjunto máximo
En el siguiente texto, CDM(C) denota el conjunto disjunto máximo de un conjunto C. Dado un conjunto C de formas, se puede encontrar una aproximación a CDM(C) mediante el siguiente algoritmo voraz: Por cada forma x que se agrega a S, se eliminan estas formas en N(x), porque están intersecadas por x y, por lo tanto, no se pueden sumar a S más adelante.
Sin embargo, algunas de estas formas se cruzan entre sí y, por lo tanto, en cualquier caso no es posible que todas estén en la solución óptima CDM(S).
El subconjunto más grande de formas que "pueden" estar en la solución óptima es "CDM(N(x))".
Por lo tanto, seleccionar una x que minimice |CDM(N(x))| minimiza la pérdida al agregar x a S. En particular, si se puede garantizar que existe una x para la que |CDM(N(x))| está limitada por una constante (póngase por caso, M), entonces este algoritmo voraz produce una aproximación constante del factor M, ya que se puede garantizar que: Tal límite superior M existe para varios casos interesantes: Cuando C es un conjunto de intervalos en una recta, M = 1 y, por lo tanto, el algoritmo voraz encuentra el CDM exacto.
Todos los demás intervalos intersecados por x deben cruzar su punto final inferior.
En contraste con el caso unidimensional, en 2 o más dimensiones el problema de hallar el CDM se vuelve NP-completo y, por lo tanto, tiene algoritmos superpolinomiales exactos o algoritmos polinomiales aproximados.
Por lo tanto, el algoritmo voraz produce una aproximación 3, es decir, encuentra un conjunto disjunto con un tamaño de al menos CDM(C)/3.
[3] El enfoque más común para encontrar un CDM es el de divide y vencerás.
Sea C un conjunto de n rectángulos paralelos a los ejes en el plano, todos con la misma altura H pero con longitudes variables.
Existe un algoritmo que encuentra un conjunto disjunto con un tamaño de al menos |CDM(C)|/(1 + 1/k) en el tiempo O( n2k−1), para cada constante k > 1.
[5] Sea C un conjunto de n rectángulos paralelos a los ejes en el plano.
El siguiente algoritmo encuentra un conjunto disjunto con un tamaño de al menos
Se conjeturó que tal aproximación podría encontrarse utilizando "cortes de guillotina".
[8]: sub.1.2 Hasta la fecha, no se sabe si existe tal separación mediante cortes con guillotina.
Existe un EATP para encontrar un CDM basado en la alineación de la cuadrícula en varios niveles.
Ha sido descubierto por dos grupos aproximadamente al mismo tiempo y descrito de dos maneras diferentes.
Por lo tanto, si todos los objetos son gruesos y están alineados con k, es posible encontrar el conjunto disjunto máximo exacto en el tiempo nO(kc) usando un algoritmo de divide y vencerás.
Comienza con una celda del árbol cuádruple que contenga todos los objetos.
Dado que el número de objetos gruesos disjuntos que intersecan el límite de cada celda del árbol cuádruple está limitado por 4kc, se puede simplemente "adivinar" qué objetos intersecan el límite en la solución óptima y luego aplicar divide y vencerás a los objetos en su interior.
Primero, escalar los objetos de modo que todos estén contenidos en el cuadrado unitario.
Entonces: Por lo tanto, el A(j) más grande tiene un tamaño de al menos: (1 − 2/k)|A*|.
Ambas versiones se pueden generalizar a d dimensiones (con diferentes relaciones de aproximación) y al caso ponderado.
Varios algoritmos de divide y vencerás se basan en el teorema del separador geométrico.
Esto permite tanto trabajar con procedimientos EATP y con algoritmos exactos subexponenciales, tal como se explica a continuación.
Si se pudiera calcular CDM(C) exactamente, sería posible hacer que la constante a sea tan baja como 2/3 mediante una selección adecuada del rectángulo separador.
Este teorema del separador permite construir los siguientes EATP: Seleccionar una constante b.
Sea C un conjunto de n discos, tal que la relación entre el radio mayor y el radio menor sea como máximo r. El siguiente algoritmo encuentra CDM(C) exactamente en el tiempo
El algoritmo es muy simple, y la parte difícil es demostrar la relación de aproximación.
Usando relajación en programación lineal, es posible encontrar un conjunto disjunto de tamaño al menos
, o un algoritmo determinista con un tiempo de ejecución más lento (pero todavía polinomial).
