Aproximación de volumen convexo

En el análisis de algoritmos , varios autores han estudiado el cálculo del volumen de cuerpos convexos de alta dimensión , un problema que también puede utilizarse para modelar muchos otros problemas en enumeración combinatoria . A menudo, estos trabajos emplean un modelo de caja negra para el cálculo, en el que la entrada la proporciona una subrutina para comprobar si un punto está dentro o fuera del cuerpo convexo, en lugar de una lista explícita de los vértices o caras de un politopo convexo . Se sabe que, en este modelo, ningún algoritmo determinista puede lograr una aproximación precisa, ^{[ 1 ] [ 2 ]} e incluso para una lista explícita de caras o vértices, el problema es #P-difícil . ^{[ 3 ]} Sin embargo, un trabajo conjunto de Martin Dyer , Alan M. Frieze y Ravindran Kannan proporcionó un esquema de aproximación aleatoria en tiempo polinomial para el problema, estableciendo un marcado contraste entre las capacidades de los algoritmos aleatorios y deterministas. ^{[ 4 ]}

El resultado principal del artículo es un algoritmo aleatorio para encontrar un${\displaystyle \varepsilon }$aproximación al volumen de un cuerpo convexo${\displaystyle K}$en${\displaystyle n}$Espacio euclidiano de -dimensiones asumiendo la existencia de un oráculo de pertenencia . El algoritmo toma un tiempo acotado por un polinomio en${\displaystyle n}$, la dimensión de${\displaystyle K}$y${\displaystyle 1/\varepsilon }$El algoritmo combina dos ideas:

• Mediante el uso de un método de Monte Carlo de cadena de Markov (MCMC), es posible generar puntos que se distribuyen aleatoriamente de forma casi uniforme dentro de un cuerpo convexo dado. El esquema básico del algoritmo es un muestreo casi uniforme desde dentro${\displaystyle K}$colocando una cuadrícula que consta de${\displaystyle n}$cubos de dimensión y realizando un paseo aleatorio sobre estos cubos. Utilizando la teoría de cadenas de Markov de mezcla rápida , demuestran que el paseo aleatorio tarda un tiempo polinomial en estabilizarse en una distribución casi uniforme. ^{[ 4 ]}
• Mediante el muestreo por rechazo , es posible comparar los volúmenes de dos cuerpos convexos, uno anidado dentro del otro, cuando sus volúmenes difieren con una diferencia mínima. La idea básica consiste en generar puntos aleatorios dentro del contorno exterior de ambos cuerpos y contar con qué frecuencia esos puntos también se encuentran dentro del contorno interior.

El cuerpo convexo dado puede aproximarse mediante una secuencia de cuerpos anidados, hasta llegar a uno de volumen conocido (una hiperesfera). Este método se utiliza para estimar el factor por el cual cambia el volumen en cada paso de la secuencia. La multiplicación de estos factores proporciona el volumen aproximado del cuerpo original.

Este trabajo les valió a sus autores el Premio Fulkerson de 1991. ^{[ 5 ]}

Aunque el tiempo de ejecución de este algoritmo es polinomial, tiene un exponente alto. Autores posteriores mejoraron el tiempo de ejecución de este método al proporcionar cadenas de Markov de mezcla más rápida para el mismo problema. ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ]}

El resultado de aproximabilidad en tiempo polinomial se ha generalizado a estructuras más complejas como la unión y la intersección de objetos. ^{[ 11 ]} Esto se relaciona con el problema de la medida de Klee .