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 diferentes grupos
El problema se conoce como el problema (discreto) clúster y es -hard. Se puede mostrar con una reducción del problema de conjunto dominante dominante que si existe un algoritmo de aproximación para el problema con entonces .
El algoritmo óptimo aproximación de 2 es muy simple e intuitivo. Uno primero elige un punto arbitrariamente y lo coloca en el conjunto 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 , que repetidamente encontrar un punto para el que la distancia se maximiza y agregarlo a . Una vez hemos terminado.
No es difícil ver que el algoritmo codicioso óptimo se ejecuta en tiempo . Esto plantea una pregunta: ¿podemos alcanzar el tiempo ? ¿Cuánto mejor podemos hacer?