Esquemas de aproximación en tiempo polinómico para el TSP euclidiano y otros problemas geométricos

Presentamos un esquema de aproximación en tiempo polinómico para el TSP euclidiano en /spl Rfr//sup 2/. Dado cualquier n nodo en el plano y /spl epsiv/>0, el esquema encuentra una aproximación de (1+/spl epsiv/)-aproximación al tour óptimo del vendedor viajero en un tiempo de n/sup 0(1//spl epsiv/)/. Cuando los nodos están en /spl Rfr//sup d/, el tiempo de ejecución aumenta a n(O/spl tilde/(log/sup d-2/n)//spl epsiv//sup d-1/). El anterior mejor algoritmo de aproximación para el problema (debido a Christofides (1976)) logra una aproximación de 3/2 en tiempo polinómico. También damos esquemas de aproximación similares para una serie de otros problemas euclidianos, incluyendo el árbol de Steiner, k-TSP, grado mínimo-k, árbol de expansión, k-MST, etc. (Esta lista puede ampliarse; nuestras técnicas son bastante generales). Los anteriores mejores algoritmos de aproximación para todos estos problemas lograron una aproximación de factor constante. Todos nuestros algoritmos también funcionan, con casi ninguna modificación, cuando la distancia se mide utilizando cualquier norma geométrica (como l/sub p/ para p/spl ges/1 u otras normas de Minkowski).