Conjunto disjunto máximo

En geometría computacional, un conjunto disjunto máximo (CDM) es el conjunto más grande de formas geométricas no superpuestas formable a partir de un conjunto dado de formas candidatas.

Cada conjunto de formas que no se superponen es un conjunto independiente en el grafo de intersección de las formas. Por lo tanto, el problema del CDM es un caso especial del problema del conjunto independiente máximo (CIM). Ambos problemas son NP-completos, pero encontrar un CDM puede ser más fácil que encontrar un CIM en dos aspectos:

Para el problema general del CIM, los algoritmos exactos más conocidos son exponenciales. En cambio, para algunos grafos de intersección geométrica, existen algoritmos subexponenciales para encontrar un CDM.^[1]
El problema general de encontrar el CIM es difícil de aproximar y ni siquiera tiene una aproximación de factor constante. Para algunos grafos de intersección geométrica, existen esquemas de aproximación de tiempo polinómico (EATPs) para encontrar un CDM.

Encontrar un CDM es importante en aplicaciones como asignación automática de etiquetas, diseño de circuitos integrados y multiplexación por división de frecuencia celular.

El problema de determinar un CDM se puede generalizar asignando un peso diferente a cada forma y buscando un conjunto disjunto con un peso total máximo.

En el siguiente texto, CDM(C) denota el conjunto disjunto máximo de un conjunto C.

Algoritmos voraces[editar]

Dado un conjunto C de formas, se puede encontrar una aproximación a CDM(C) mediante el siguiente algoritmo voraz:

INICIALIZACIÓN: Inicializar un conjunto vacío, S.
BÚSQUEDA: Para cada forma xi en C:
1. Calcular J(xi), el subconjunto de todas las formas en C que intersecan a xi (incluido el propio xi).
2. Asignar N(xi) igual a las formas numéricas en J(xi).
3. Elegir cualquier xj tal que N(xj) sea un máximo, es decir, una forma que toque tantas formas como cualquier otra.
4. De todas las formas xi que intersecan a xj (incluida la propia xj), seleccionar la forma x que toca la menor cantidad de otras formas, es decir, un x tal que N(x) es un mínimo.
Agregar x a S.
Eliminar x de C y eliminar J(x) y N(x).
Si hay formas en C, regresar a BÚSQUEDA.
FIN: devolver el conjunto S.

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:

|S|\geq {\frac {|CDM(C)|}{M}}

Tal límite superior M existe para varios casos interesantes:

Intervalos unidimensionales: algoritmo polinómico exacto[editar]

Cuando C es un conjunto de intervalos en una recta, M = 1 y, por lo tanto, el algoritmo voraz encuentra el CDM exacto. Para ver esto, supóngase sin pérdida de generalidad que los intervalos son verticales, y sea x el intervalo con el punto final inferior más alto. Todos los demás intervalos intersecados por x deben cruzar su punto final inferior. Por lo tanto, todos los intervalos en N(x) se cruzan entre sí y CDM(N(x)) tiene un tamaño de como máximo 1 (véase la figura).

Por lo tanto, en el caso unidimensional, el CDM se puede encontrar exactamente en el tiempo O(n log n):^[2]

Ordenar los intervalos en orden ascendente de sus puntos finales inferiores (esto lleva tiempo O(n log n)).
Agregar un intervalo con el punto final inferior más alto y eliminar todos los intervalos que lo cruzan.
Continuar hasta que no queden intervalos.

Este algoritmo es análogo al de la solución de la fecha límite más temprana en primera programación en el problema de programación de intervalos.

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.

Formas gruesas: aproximaciones de factor constante[editar]

Cuando C es un conjunto de discos unitarios, M=3,^[3] porque el disco más a la izquierda (el disco cuyo centro tiene la coordenada x más pequeña) interseca como máximo otros 3 discos disjuntos (véase la imagen). 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.

De manera similar, cuando C es un conjunto de cuadrados unitarios paralelos a los ejes, M=2.

Cuando C es un conjunto de discos de tamaño arbitrario, M=5, porque el disco con el radio más pequeño interseca como máximo a otros 5 discos disjuntos (véase la figura).

De manera similar, cuando C es un conjunto de cuadrados paralelos a los ejes de tamaño arbitrario, M = 4.

Se pueden calcular otras constantes para otros polígonos regulares.^[3]

Algoritmos de divide y vencerás[editar]

El enfoque más común para encontrar un CDM es el de divide y vencerás. Un algoritmo típico de este enfoque se parece al siguiente:

Dividir el conjunto de formas dado en dos o más subconjuntos, de modo que las formas de cada subconjunto no puedan superponerse a las formas de otros subconjuntos debido a consideraciones geométricas.
Encontrar recursivamente el CDM en cada subconjunto por separado.
Devolver la unión de los CDM de todos los subconjuntos.

El principal desafío de este enfoque es encontrar una forma geométrica de dividir el conjunto en subconjuntos. Esto puede requerir descartar una pequeña cantidad de formas que no encajan en ninguno de los subconjuntos, como se explica en las siguientes subsecciones.

Rectángulos paralelos al eje con la misma altura: aproximación 2[editar]

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. El siguiente algoritmo encuentra un conjunto disjunto con un tamaño de al menos |CDM(C)|/2 en el tiempo O(n log n):^[2]

Dibujar m líneas horizontales, tales que:
1. La separación entre dos líneas es estrictamente mayor que H.
2. Cada línea interseca al menos un rectángulo (por lo tanto, m ≤ n).
3. Cada rectángulo es intersecado por exactamente una recta.
Dado que la altura de todos los rectángulos es H, no es posible que un rectángulo sea intersecado por más de una recta. Por lo tanto, las líneas rectas dividen el conjunto de rectángulos en m subconjuntos ( $R_{i},\ldots ,R_{m}$ ): cada subconjunto incluye los rectángulos intersecados por una sola recta.
Para cada subconjunto $R_{i}$ , calcular un CDM $M_{i}$ exacto utilizando el algoritmo voraz unidimensional (véase arriba).
Por construcción, los rectángulos en ( $R_{i}$ $R_{i}$ ) solo pueden intersecar rectángulos en $R_{i+1}$ $R_{i+1}$ o en $R_{i-1}$ $R_{i-1}$ . Por lo tanto, cada una de las dos uniones siguientes es un conjunto disjunto:
- Unión de CDM impares: $M_{1}\cup M_{3}\cup \cdots$
- Unión de CDM pares: $M_{2}\cup M_{4}\cup \cdots$
Devolver la mayor de estas dos uniones. Su tamaño debe ser al menos |CDM|/2.

Rectángulos paralelos al eje con la misma altura: EATP[editar]

Sea C un conjunto de n rectángulos paralelos a los ejes en el plano, todos con la misma altura 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( n^2k−1), para cada constante k > 1.^[2]

El algoritmo es una mejora de la aproximación 2 mencionada anteriormente, combinando programación dinámica con la técnica de desplazamiento de Hochbaum y Maass.^[4]

Este algoritmo se puede generalizar a d dimensiones. Si las etiquetas tienen el mismo tamaño en todas las dimensiones excepto una, es posible encontrar una aproximación similar aplicando programación dinámica en una de las dimensiones. Esto también reduce el tiempo a n^O(1/e).^[5]

Rectángulos paralelos al eje: aproximación de factor logarítmico[editar]

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 ${\frac {|CDM(C)|}{\log {n}}}$ en el tiempo $O(n\log {n})$ :^[2]

INICIALIZACIÓN: ordenar los bordes horizontales de los rectángulos dados por su coordenada y, y los bordes verticales por su coordenada x (este paso lleva tiempo O(n log n)).
CONDICIÓN DE DETENCIÓN: si hay como máximo n ≤ 2 formas, calcular el CDM directamente y regresar.
PARTE RECURSIVA:
1. Sea $x_{\mathrm {med} }$ la coordenada x media.
2. Dividir los rectángulos del problema en tres grupos según su relación con la recta $x=x_{\mathrm {med} }$ : los que están completamente a su izquierda ( $R_{\mathrm {left} }$ ), los que están completamente a su derecha ( $R_{\mathrm {right} }$ ) y los que intersecan con ella ( $R_{\mathrm {int} }$ ). Por construcción, las cardinalidades de $R_{\mathrm {left} }$ y $R_{\mathrm {right} }$ son como máximo n/2.
3. Calcular recursivamente un CDM aproximado en $R_{\mathrm {left} }$ ( $M_{\mathrm {left} }$ ) y en $R_{\mathrm {right} }$ ( $M_{\mathrm {right} }$ ), y calcular su unión. Por construcción, los rectángulos en $M_{\mathrm {left} }$ y $M_{\mathrm {right} }$ son todos disjuntos, por lo que $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ es un conjunto disjunto.
4. Calcular un CDM exacto en $R_{\mathrm {int} }$ ( $M_{\mathrm {int} }$ ). Dado que todos los rectángulos en $R_{\mathrm {int} }$ intersecan una sola línea recta vertical $x=x_{\mathrm {med} }$ , este cálculo es equivalente a encontrar un CDM a partir de un conjunto de intervalos y se puede resolver exactamente en el tiempo O(n log n) (véase arriba).
Devuelve $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ o $M_{\mathrm {int} }$ , el que sea mayor.

Se puede demostrar por inducción que, en el último paso, $M_{\mathrm {left} }\cup M_{\mathrm {right} }$ o $M_{\mathrm {int} }$ tienen una cardinalidad de al menos ${\frac {|CDM(C)|}{\log {n}}}$ .

Chalermsookk y Chuzoy^[6] mejoraron el factor a $O(\log {\log {n}})$ .

Chalermsookk y Walczak^[7] presentaron un algoritmo de aproximación $O(\log {\log {n}})$ a un entorno más general, en el que cada rectángulo tiene un "peso", y el objetivo es encontrar un conjunto independiente de peso total máximo.

Rectángulos paralelos al eje: aproximación de factor constante[editar]

Durante mucho tiempo no se supo si existe una aproximación de factor constante para rectángulos paralelos a sus ejes de diferentes longitudes y alturas. Se conjeturó que tal aproximación podría encontrarse utilizando "cortes de guillotina". En particular, si existe un corte con guillotina de rectángulos paralelos a los ejes en los que los rectángulos $\Omega (n)$ están separados, entonces se puede utilizar en un enfoque de programación dinámica para encontrar una aproximación de factor constante al CDM.^[8]^: sub.1.2

Hasta la fecha, no se sabe si existe tal separación mediante cortes con guillotina. Sin embargo, existen algoritmos de aproximación de factor constante que utilizan cortes pero sin guillotina:

Joseph S. B. Mitchell presentó un algoritmo de aproximación de 10 factores. Su algoritmo se basa en dividir el plano en "rectángulos recortados en las esquinas".^[9]
Gálvez, Khan, Mari, Mömke, Pittu y Wiese presentaron una parte del algoritmo basado en particionar el plano en una clase más general de polígonos. Esto simplifica el análisis y mejora la aproximación a 6 factores. Además, mejoraron la aproximación al factor 3^[10] y luego al factor (2+ε).^[11]

Objetos gruesos de idéntico tamaño: EATP[editar]

Sea C un conjunto de n cuadrados o círculos de tamaño idéntico. Hochbaum y Maass^[4] presentaron un esquema de aproximación de tiempo polinómico para encontrar un CDM utilizando una estrategia simple de cuadrícula desplazada. El procedimiento encuentra una solución dentro de (1 − ε) del máximo en el tiempo n^O(1/ε²), de tiempo y espacio lineal. La estrategia se generaliza a cualquier colección de objeto grueso de aproximadamente el mismo tamaño (es decir, cuando la relación de tamaño máximo a mínimo está limitada por una constante).

Objetos gruesos de cualquier tamaño: EATP[editar]

Sea C un conjunto de n objetos gruesos, como cuadrados o círculos, de tamaños arbitrarios. 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.

Partición nivelada[editar]

Un algoritmo de Erlebach, Jansen y Seidel^[12] encuentra un conjunto disjunto con un tamaño de al menos (1 − 1/k)² · |CDM(C)| en el tiempo n^O(k²), para cada constante k > 1. Funciona de la siguiente manera:

Escalar los discos para que el disco más pequeño tenga un diámetro de 1. Dividir los discos en niveles, según el logaritmo de su tamaño. Es decir, el nivel j contiene todos los discos con diámetro entre (k + 1)^j y (k + 1)^j+1, para j ≤ 0 (el disco más pequeño está en el nivel 0).
Para cada nivel j, imponer una cuadrícula en el plano que consta de líneas que están (k + 1)^j+1 separadas entre sí. Por construcción, cada disco puede cruzar como máximo una línea horizontal y una línea vertical desde su nivel.
Para cada r, s entre 0 y k, definir D(r,s) como el subconjunto de discos que no son cruzados por cualquier línea horizontal cuyo índice módulo k sea r, ni por ninguna línea vertical cuyo índice módulo k sea s. Por el principio del palomar, existe al menos un par (r,s) tal que $|\mathrm {CDM} (D(r,s))|\geq (1-{\frac {1}{k}})^{2}\cdot |\mathrm {CDM} |$ , es decir, se puede encontrar el CDM solo en D(r,s) y perder solo una pequeña fracción de los discos en la solución óptima:
Para todos los k² valores posibles de r,s (0 ≤ r,s < k), calcular D(r,s) usando programación dinámica.
Devuelve el mayor de estos conjuntos k².

Árboles cuádruples desplazados[editar]

Un algoritmo de Chan^[5] encuentra un conjunto disjunto con un tamaño de al menos (1 − 2/k)·|CDM(C)| en el tiempo n^O(k), para cada constante k > 1.

El algoritmo utiliza árboles cuadrados desplazados. El concepto clave del algoritmo es el de la "alineación" con la cuadrícula del árbol cuádruple. Un objeto de tamaño r se llama k-alineado (donde k ≥ 1 es una constante) si está dentro de una celda de árbol cuádruple de tamaño como máximo kr(R ≤ kr).

Por definición, un objeto alineado con k que interseca el límite de una celda de cuatro árboles de tamaño R debe tener un tamaño de al menos R/k (r > R/k). El límite de una celda de tamaño R puede estar cubierto por 4k cuadrados de tamaño R/k. Por lo tanto, el número de objetos grasos disjuntos que cruzan el límite de esa celda es como máximo 4kc, donde c es una constante que mide el grosor de los objetos.

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 n^O(kc) usando un algoritmo de divide y vencerás. Comienza con una celda del árbol cuádruple que contenga todos los objetos. Luego, se divide de forma recursiva en celdas del árbol cuádruple más pequeñas, se encuentra el máximo en cada celda más pequeña y se combinan los resultados para obtener el máximo en la celda más grande. 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.

Si casi todos los objetos están alineados con k, se puede simplemente descartar los objetos que no están alineados con k y encontrar un conjunto máximo disjunto de los objetos restantes en el tiempo n^O(k). Esto da como resultado una aproximación (1 − e), donde e es la fracción de objetos que no están alineados con k.

Si la mayoría de los objetos no están alineados con k, se puede intentar alinearlos con k''desplazando la cuadrícula en múltiplos de (1/k,1/ k). Primero, escalar los objetos de modo que todos estén contenidos en el cuadrado unitario. Luego, considerar los k desplazamientos de la cuadrícula: (0,0), (1/k,1/k), (2/k,2/ k), ..., ((k − 1)/k,(k − 1)/k' '). Es decir, para cada j en {0,...,k − 1}, considerar un desplazamiento de la cuadrícula en (j/k,j/k). Es posible demostrar que cada etiqueta estará alineada con 2k para al menos k −2 valores de j. Ahora, para cada j, descartar los objetos que no estén alineados con k en los saltos de (j/k,j/k) y encontrar el conjunto primario disjunto máximo de los objetos restantes. Llamar a ese conjunto A(j), y llamar al conjunto disjunto máximo real es A*. Entonces:

\sum _{j=0,\ldots ,k-1}{|A(j)|}\geq (k-2)|A*|

Por lo tanto, el A(j) más grande tiene un tamaño de al menos: (1 − 2/k)|A*|. El valor de retorno del algoritmo es el mayor A(j). El factor de aproximación es (1 − 2/k) y el tiempo de ejecución es n^O(k). Se puede hacer que el factor de aproximación sea tan pequeño como se quiera, por lo que este es un EATP.

Ambas versiones se pueden generalizar a d dimensiones (con diferentes relaciones de aproximación) y al caso ponderado.

Algoritmos de separador geométrico[editar]

Varios algoritmos de divide y vencerás se basan en el teorema del separador geométrico. Un separador geométrico es una línea o forma que separa un conjunto determinado de formas en dos subconjuntos más pequeños, de modo que el número de formas perdidas durante la división es relativamente pequeño. Esto permite tanto trabajar con procedimientos EATP y con algoritmos exactos subexponenciales, tal como se explica a continuación.

Objetos gruesos con tamaños arbitrarios: EATP usando separadores geométricos[editar]

Sea C un conjunto de nobjetos gruesos, como cuadrados o círculos, de tamaños arbitrarios. Chan^[5] describió un algoritmo que encuentra un conjunto disjunto con un tamaño de al menos (1 − O(√b))·|CDM(C)| en el tiempo n^O(b), para cada constante b > 1.

El algoritmo se basa en el siguiente teorema del separador geométrico, que se puede demostrar de manera similar a la prueba de la existencia de un separador geométrico para cuadrados disjuntos:

Para cada conjunto C de objetos gruesos, hay un rectángulo que divide C en tres subconjuntos de objetos: C_inside, C_outside y C_boundary, tales que:

|CDM(C_inside)| ≤ a|CDM(C)|
|CDM(C_outside)| ≤ a|CDM(C)|
|CDM(C_boundary)| c√|CDM(C)|

donde a y c son constantes. 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. Pero como solo se puede aproximar el CDM(C) mediante un factor constante, la constante a debe ser mayor. Afortunadamente, a sigue siendo una constante independiente de |C|.

Este teorema del separador permite construir los siguientes EATP:

Seleccionar una constante b. Consultar todas las combinaciones posibles de hasta b + 1 etiquetas.

Si |CDM(C)| tiene un tamaño de como máximo b (es decir, todos los conjuntos de b+1 etiquetas no están separados), entonces simplemente devolver ese CDM y salir. Este paso lleva un tiempo n^O(b).
De lo contrario, utilizar un separador geométrico para separar C en dos subconjuntos. Encontrar el CDM aproximado en C_inside y C_outside por separado y devolver su combinación como el CDM aproximado en C.

Sea E(m) el error del algoritmo anterior cuando el tamaño óptimo del CDM es CDM(C) = m. Cuando m ≤ b, el error es 0 porque el conjunto disjunto máximo se calcula exactamente; cuando m > b, el error aumenta como máximo c√m el número de etiquetas intersecadas por el separador. El peor caso para el algoritmo es cuando la división en cada paso está en la proporción máxima posible, que es a:(1 − a). Por tanto, la función de error satisface la siguiente relación de recurrencia:

E(m)=0\ \ \ \ {\text{if }}m\leq b

E(m)=E(a\cdot m)+E((1-a)\cdot m)+c\cdot {\sqrt {m}}{\text{if }}m>b

La solución a esta recurrencia es:

E(m)=({\frac {0}{b}}+{\frac {c}{{\sqrt {b}}({\sqrt {a}}+{\sqrt {1-a}}-1)}})\cdot m-{\frac {c}{{\sqrt {a}}+{\sqrt {1-a}}-1}}\cdot {\sqrt {m}}.

es decir, $E(m)=O(m/{\sqrt {b}})$ . Se puede hacer que el factor de aproximación sea tan pequeño como se quiera mediante una selección adecuada de b.

Este EATP ahorra más espacio que el EATP basado en árboles cuádruples y puede manejar una generalización en la que los objetos pueden deslizarse, pero no puede manejar el caso ponderado.

Discos con una relación de tamaño acotada: algoritmo subexponencial exacto[editar]

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 $2^{O(r\cdot {\sqrt {n}})}$ .^[13]

El algoritmo se basa en un separador geométrico acotado por ancho en el conjunto Q de los centros de todos los discos en C. Este teorema del separador permite construir el siguiente algoritmo exacto:

Encontrar una línea recta separadora tal que como máximo 2n/3 centros estén a su derecha (C_right), como máximo 2n/3 centros estén a su izquierda (C _left), y como máximo los O(√n) centros están a una distancia inferior a r/2 de la línea recta (C_int).
Considerar todos los posibles subconjuntos no superpuestos de C_int. Hay como máximo $2^{O(r\cdot {\sqrt {n}})}$ subconjuntos de este tipo. Para cada uno de estos subconjuntos, calcular recursivamente el CDM de C_left y el CDM de C_right y devolver el conjunto combinado más grande.

El tiempo de ejecución de este algoritmo satisface la siguiente relación de recurrencia:

T(1)=1

T(n)=2^{O(r\cdot {\sqrt {n}})}T\left({\frac {2n}{3}}\right){\text{if }}n>1

La solución a esta recurrencia es:

T(n)=2^{O(r\cdot {\sqrt {n}})}

Algoritmos de búsqueda local[editar]

Pseudodiscos: EATP[editar]

Un conjunto de pseudodiscos es un conjunto de objetos en el que los límites de cada par de objetos se cruzan como máximo dos veces (téngase en cuenta que esta definición se refiere a una colección completa y no dice nada sobre las formas específicas de los objetos de la colección). Un conjunto de pseudodiscos tiene una complejidad de unión acotada, es decir, el número de puntos de intersección en el límite de la unión de todos los objetos es lineal con respecto al número de objetos. Por ejemplo, un conjunto de cuadrados o círculos de tamaños arbitrarios es un conjunto de pseudodiscos.

Sea C un conjunto de pseudodiscos con n objetos. Un algoritmo de búsqueda local de Chan y Har-Peled^[14] permite encontrar un conjunto disjunto de tamaño al menos $(1-O({\frac {1}{\sqrt {b}}}))\cdot |CDM(C)|$ en el tiempo $O(n^{b+3})$ , para cada constante entera $b\geq 0$ :

INICIALIZACIÓN: inicializar un conjunto vacío, $S$ .
BÚSQUEDA: recorrer todos los subconjuntos de $C-S$ $C-S$ cuyo tamaño esté entre 1 y $b+1$ $b+1$ . Para cada uno de esos subconjuntos X:
- Verificar que X sea independiente (de lo contrario, pasar al siguiente subconjunto).
- Calcular el conjunto Y de objetos en S que intersecan a X.
- Si es $|Y|<|X|$ , eliminar Y de S e insertar X: $S:=S-Y+X$ .
FIN: devolver el conjunto S.

Cada intercambio en el paso de búsqueda aumenta el tamaño de S en al menos 1 y, por lo tanto, puede ocurrir como máximo n veces.

El algoritmo es muy simple, y la parte difícil es demostrar la relación de aproximación.^[14]

Véase también al respecto el trabajo de P. K. Agarwal y de N. H. Mustafa.^[15]

Algoritmos de relajación en programación lineal[editar]

Pseudodiscos: EATP[editar]

Sea C un conjunto de pseudodiscos con n objetos y complejidad de unión u. Usando relajación en programación lineal, es posible encontrar un conjunto disjunto de tamaño al menos ${\frac {n}{u}}\cdot |CDM(C)|$ . Esto es posible con un algoritmo aleatorio que tiene una alta probabilidad de éxito y un tiempo de ejecución $O(n^{3})$ , o un algoritmo determinista con un tiempo de ejecución más lento (pero todavía polinomial). Este algoritmo se puede generalizar al caso ponderado.^[14]

Otras clases de formas para las que se conocen aproximaciones[editar]

Segmentos de recta en el plano bidimensional.^[15]^[16]
Formas convexas bidimensionales arbitrarias.^[15]
Curvas con un número acotado de puntos de intersección.^[16]

Enlaces externos[editar]

Referencias[editar]

↑ Ravi, S. S.; Hunt, H. B. (1987). «An application of the planar separator theorem to counting problems». Information Processing Letters 25 (5): 317. doi:10.1016/0020-0190(87)90206-7. , Smith, W. D.; Wormald, N. C. (1998). «Geometric separator theorems and applications». Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). p. 232. ISBN 978-0-8186-9172-0. S2CID 17962961. doi:10.1109/sfcs.1998.743449.
↑ ^a ^b ^c ^d Agarwal, P. K.; Van Kreveld, M.; Suri, S. (1998). «Label placement by maximum independent set in rectangles». Computational Geometry 11 (3–4): 209. doi:10.1016/s0925-7721(98)00028-5. hdl:1874/18908.
↑ ^a ^b Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J. (1995). «Simple heuristics for unit disk graphs». Networks 25 (2): 59. arXiv:math/9409226. doi:10.1002/net.3230250205.
↑ ^a ^b Hochbaum, D. S.; Maass, W. (1985). «Approximation schemes for covering and packing problems in image processing and VLSI». Journal of the ACM 32: 130-136. S2CID 2383627. doi:10.1145/2455.214106.
↑ ^a ^b ^c Chan, T. M. (2003). «Polynomial-time approximation schemes for packing and piercing fat objects». Journal of Algorithms 46 (2): 178-189. doi:10.1016/s0196-6774(02)00294-8. «citeseerx: 10.1.1.21.5344».
↑ Chalermsook, P.; Chuzhoy, J. (2009). «Maximum Independent Set of Rectangles». Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 892. ISBN 978-0-89871-680-1. doi:10.1137/1.9781611973068.97.
↑ Chalermsook, Parinya; Walczak, Bartosz (1 de enero de 2021), «Coloring and Maximum Weight Independent Set of Rectangles», Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings (Society for Industrial and Applied Mathematics): 860-868, ISBN 978-1-61197-646-5, S2CID 220525811, arXiv:2007.07880, doi:10.1137/1.9781611976465.54, consultado el 29 de septiembre de 2022 .
↑ Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1-19. ISBN 978-3-939897-89-7. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1.
↑ Mitchell, Joseph S. B. (2021-06-25). «Approximating Maximum Independent Set for Rectangles in the Plane». arXiv:2101.00326 [cs.CG].
↑ Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Pittu, Madhusudhan Reddy; Wiese, Andreas (1 de enero de 2022), «A 3-Approximation Algorithm for Maximum Independent Set of Rectangles», Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings (Society for Industrial and Applied Mathematics): 894-905, ISBN 978-1-61197-707-3, S2CID 235265867, doi:10.1137/1.9781611977073.38, consultado el 29 de septiembre de 2022 .
↑ Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Reddy, Madhusudhan; Wiese, Andreas (2021-09-26). «A (2+\epsilon)-Approximation Algorithm for Maximum Independent Set of Rectangles». arXiv:2106.00623 [cs.CG].
↑ Erlebach, T.; Jansen, K.; Seidel, E. (2005). «Polynomial-Time Approximation Schemes for Geometric Intersection Graphs». SIAM Journal on Computing 34 (6): 1302. doi:10.1137/s0097539702402676.
↑ Fu, B. (2011). «Theory and application of width bounded geometric separators». Journal of Computer and System Sciences 77 (2): 379-392. doi:10.1016/j.jcss.2010.05.003.
↑ ^a ^b ^c Chan, T. M.; Har-Peled, S. (2012). «Approximation Algorithms for Maximum Independent Set of Pseudo-Disks». Discrete & Computational Geometry 48 (2): 373. S2CID 38183751. arXiv:1103.1431. doi:10.1007/s00454-012-9417-5.
↑ ^a ^b ^c Agarwal, P. K.; Mustafa, N. H. (2006). «Independent set of intersection graphs of convex objects in 2D». Computational Geometry 34 (2): 83. doi:10.1016/j.comgeo.2005.12.001.
↑ ^a ^b Fox, J.; Pach, J. N. (2011). «Computing the Independence Number of Intersection Graphs». Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1161. ISBN 978-0-89871-993-2. S2CID 15850862. doi:10.1137/1.9781611973082.87. «citeseerx: 10.1.1.700.4445».

Datos: Q17163363

[1] Ravi, S. S.; Hunt, H. B. (1987). «An application of the planar separator theorem to counting problems». Information Processing Letters 25 (5): 317. doi:10.1016/0020-0190(87)90206-7. , Smith, W. D.; Wormald, N. C. (1998). «Geometric separator theorems and applications». Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280). p. 232. ISBN 978-0-8186-9172-0. S2CID 17962961. doi:10.1109/sfcs.1998.743449.

[Agarwal1998-2] Agarwal, P. K.; Van Kreveld, M.; Suri, S. (1998). «Label placement by maximum independent set in rectangles». Computational Geometry 11 (3–4): 209. doi:10.1016/s0925-7721(98)00028-5. hdl:1874/18908.

[Marathe1995-3] Marathe, M. V.; Breu, H.; Hunt, H. B.; Ravi, S. S.; Rosenkrantz, D. J. (1995). «Simple heuristics for unit disk graphs». Networks 25 (2): 59. arXiv:math/9409226. doi:10.1002/net.3230250205.

[HochbaumMaass1985-4] Hochbaum, D. S.; Maass, W. (1985). «Approximation schemes for covering and packing problems in image processing and VLSI». Journal of the ACM 32: 130-136. S2CID 2383627. doi:10.1145/2455.214106.

[Chan2003-5] Chan, T. M. (2003). «Polynomial-time approximation schemes for packing and piercing fat objects». Journal of Algorithms 46 (2): 178-189. doi:10.1016/s0196-6774(02)00294-8. «citeseerx: 10.1.1.21.5344».

[6] Chalermsook, P.; Chuzhoy, J. (2009). «Maximum Independent Set of Rectangles». Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 892. ISBN 978-0-89871-680-1. doi:10.1137/1.9781611973068.97.

[7] Chalermsook, Parinya; Walczak, Bartosz (1 de enero de 2021), «Coloring and Maximum Weight Independent Set of Rectangles», Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings (Society for Industrial and Applied Mathematics): 860-868, ISBN 978-1-61197-646-5, S2CID 220525811, arXiv:2007.07880, doi:10.1137/1.9781611976465.54, consultado el 29 de septiembre de 2022 .

[8] Abed, Fidaa; Chalermsook, Parinya; Correa, José; Karrenbauer, Andreas; Pérez-Lantero, Pablo; Soto, José A.; Wiese, Andreas (2015). On Guillotine Cutting Sequences. pp. 1-19. ISBN 978-3-939897-89-7. doi:10.4230/LIPIcs.APPROX-RANDOM.2015.1.

[9] Mitchell, Joseph S. B. (2021-06-25). «Approximating Maximum Independent Set for Rectangles in the Plane». arXiv:2101.00326 [cs.CG].

[10] Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Pittu, Madhusudhan Reddy; Wiese, Andreas (1 de enero de 2022), «A 3-Approximation Algorithm for Maximum Independent Set of Rectangles», Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings (Society for Industrial and Applied Mathematics): 894-905, ISBN 978-1-61197-707-3, S2CID 235265867, doi:10.1137/1.9781611977073.38, consultado el 29 de septiembre de 2022 .

[11] Gálvez, Waldo; Khan, Arindam; Mari, Mathieu; Mömke, Tobias; Reddy, Madhusudhan; Wiese, Andreas (2021-09-26). «A (2+\epsilon)-Approximation Algorithm for Maximum Independent Set of Rectangles». arXiv:2106.00623 [cs.CG].

[Erlebach2005-12] Erlebach, T.; Jansen, K.; Seidel, E. (2005). «Polynomial-Time Approximation Schemes for Geometric Intersection Graphs». SIAM Journal on Computing 34 (6): 1302. doi:10.1137/s0097539702402676.

[Fu-13] Fu, B. (2011). «Theory and application of width bounded geometric separators». Journal of Computer and System Sciences 77 (2): 379-392. doi:10.1016/j.jcss.2010.05.003.

[ChanHarPeled2012-14] Chan, T. M.; Har-Peled, S. (2012). «Approximation Algorithms for Maximum Independent Set of Pseudo-Disks». Discrete & Computational Geometry 48 (2): 373. S2CID 38183751. arXiv:1103.1431. doi:10.1007/s00454-012-9417-5.

[am06-15] Agarwal, P. K.; Mustafa, N. H. (2006). «Independent set of intersection graphs of convex objects in 2D». Computational Geometry 34 (2): 83. doi:10.1016/j.comgeo.2005.12.001.

[fp11-16] Fox, J.; Pach, J. N. (2011). «Computing the Independence Number of Intersection Graphs». Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1161. ISBN 978-0-89871-993-2. S2CID 15850862. doi:10.1137/1.9781611973082.87. «citeseerx: 10.1.1.700.4445».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]