Graham y Sloane estudiado el problema de minimzing el segundo momento de discos en el plano, es decir, minimizar
$$ U = \frac{1}{d^2} \sum_{i=1}^{n} || \mathbf{p}_i - \bar{\mathbf{p}} ||^2 $$
s.t. $||\mathbf{p}_i - \mathbf{p}_j|| \geq d$ todos los $i,j$.
Que enfoque el problema de forma heurística, y el algoritmo que se usa es: empezar con dos discos adyacentes y, a continuación, mantenga la adición de la $(n+1)$th disco de tal manera que (a) es tangencial a al menos uno de los otros $n$ discos, y (b) se minimiza $U_{n+1}|U_n$.
Algoritmos como estos son los llamados "algoritmos voraces," y mientras no garantizan soluciones óptimas, tienden a dar buenas aproximaciones cuando la aptitud del paisaje es lo suficientemente bueno.
Ahora, me gustaría demostrar que este algoritmo está "justificado" (no es correcto - no lo es! - justificado), es decir, que para un mínimo de $U$, cada disco debe ser tangencial a al menos otro disco.
Mientras que esto es intuitivamente "obvio" me estoy encontrando difícil el enfoque formal.
Estoy pensando que a lo largo de las líneas de "mostrar que si existe una solución óptima cuando un disco no es tangencial a otro disco, entonces la solución puede ser mejorado por lo que es así." Pero, ¿cómo acerca de situaciones como estas:
Mover el disco a la mitad claramente aumentar el $U$. Por supuesto, que voy a decir, esto es debido a que el arreglo no es óptima en el primer lugar; pero, de nuevo, sólo sabemos intuitivamente, por lo tanto, estamos de nuevo al cuadrado uno.
Mi pensamiento es el uso de la inducción, pero esto nos lleva de nuevo al problema del algoritmo voraz: una solución para $n$ no dice nada acerca de la solución para $n+1$.
Soy muy consciente de que el círculo de embalaje problemas son, en general, muy difícil; de hecho, las soluciones exactas sólo existen para muy pequeño $n$. Sin embargo, creo que una prueba de tal observación básicas que probablemente debería estar dentro de alcance (si no lo sabe ya). Cualquier idea será muy apreciada.
