Tiempo de ejecución del algoritmo de aproximación

16

Se nos da un conjunto de puntos bidimensionales un entero . Debemos encontrar una colección de círculos que encierren todos los puntos de modo que el radio del círculo más grande sea lo más pequeño posible. En otras palabras, debemos encontrar un conjunto de puntos centrales de modo que la función de costo está minimizado. Aquí, D denota la distancia euclidiana entre un punto de entrada p_i y un punto central c_j . Cada punto se asigna al centro del grupo más cercano agrupando los vértices en kk k n C = { c 1 , c 2 , , c k } k costo ( C ) = max i min j D ( p i , c j ) D p i c j k|P|=nkknC={c1,c2,,ck}kcost(C)=maximinjD(pi,cj)Dpicjk diferentes grupos

El problema se conoce como el problema (discreto) k clúster y es NP -hard. Se puede mostrar con una reducción del problema de conjunto dominante dominante NP que si existe un algoritmo de aproximación ρ para el problema con ρ<2 entonces P=NP .

El algoritmo óptimo 2 aproximación de 2 es muy simple e intuitivo. Uno primero elige un punto pP arbitrariamente y lo coloca en el conjunto C de centros de clúster. Luego, se elige el siguiente centro de agrupación de modo que esté lo más alejado posible de todos los demás centros de agrupación. Entonces, mientras |C|<k , que repetidamente encontrar un punto jP para el que la distancia D(j,C) se maximiza y agregarlo a C . Una vez |C|=k hemos terminado.

No es difícil ver que el algoritmo codicioso óptimo se ejecuta en tiempo O(nk) . Esto plantea una pregunta: ¿podemos alcanzar el tiempo o(nk) ? ¿Cuánto mejor podemos hacer?

Juho
fuente

Respuestas:

7

De hecho, el problema se puede ver geométricamente de una manera que nos gustaría cubrir los puntos con bolas, donde el radio de la bola más grande se minimiza.Vk

O(nk) es bastante simple de lograr, pero uno puede hacerlo mejor. Feder y Greene, algoritmos óptimos para la agrupación aproximada, 1988 logran un tiempo de ejecución deΘ(nlogk) utilizando estructuras de datos más inteligentes y muestran que esto es óptimo en el modelo de árbol de decisión algebraico.

Juho
fuente
1

Mi pregunta: ¿Hay alguna manera de hacer que la estrategia de selección ambiciosa se ejecute en tiempo?o(|V|2)

Me parece que lo describiste. En caso de que haya leído demasiado lejos en su descripción, esto es lo que he entendido. Tener una estructura de datos asociativa asociar cada elemento de con la suma de la distancia a los elementos de S . Esta estructura de datos se puede inicializar a un costo O ( | V | ) con la distancia a p y esta inicialización puede producir el siguiente elemento como un efecto secundario sin aumentar la complejidad. Se puede actualizar después de la selección de un nuevo elemento a un costo de O ( | V | ) , produciendo nuevamente el siguiente elemento como efecto secundario. Repita para obtener SVSO(|V|)pO(|V|)S. La complejidad resultante es .O(k|V|)

Un programador
fuente
1
Pero tenga en cuenta el límite en : en el peor de los casos, puede ser tan grande como | V | . Sospecho que hay estructuras de datos que alcanzan límites aún mejores, pero realmente no lo sé. k|V|
Juho
Vaya, y no O en tu pregunta. (Tenga en cuenta que en su pregunta vuelve a k 3 , por lo que esto debería ser una mejora). Lo que propongo no usa el hecho de que estás trabajando en un espacio euclidiano, creo que tendrás que usarlo para hacerlo mejor, pero actualmente no veo cómo. oOk3
Programador