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 se puede utilizar para modelar muchos otros problemas en enumeración combinatoria . A menudo, estos trabajos utilizan un modelo de caja negra de cálculo en el que la entrada se proporciona mediante una subrutina para probar si un punto está dentro o fuera del cuerpo convexo, en lugar de mediante un listado explícito 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 un listado explícito de caras o vértices el problema es #P-hard . ^[3] Sin embargo, un trabajo conjunto de Martin Dyer , Alan M. Frieze y Ravindran Kannan proporcionó un esquema de aproximación de tiempo polinomial aleatorio para el problema, proporcionando un marcado contraste entre las capacidades de los algoritmos aleatorios y deterministas. ^[4]

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

• Al utilizar un método de Monte Carlo de cadenas de Markov (MCMC), es posible generar puntos que se distribuyen de manera casi uniforme y aleatoria dentro de un cuerpo convexo determinado. El esquema básico del algoritmo es un muestreo casi uniforme desde dentro colocando una cuadrícula que consiste en cubos de dimensión 1 y haciendo un recorrido aleatorio sobre estos cubos. Al utilizar la teoría de la mezcla rápida de cadenas de Markov , demuestran que se necesita un tiempo polinomial para que el recorrido aleatorio se estabilice y se convierta en una distribución casi uniforme. ^[4] ${\displaystyle K}$ ${\displaystyle n}$
• Al utilizar el muestreo por rechazo , es posible comparar los volúmenes de dos cuerpos convexos, uno anidado dentro de otro, cuando sus volúmenes están dentro de un pequeño factor entre sí. La idea básica es generar puntos aleatorios dentro del exterior de los dos cuerpos y contar con qué frecuencia esos puntos también están dentro del cuerpo interior.

El cuerpo convexo dado se puede aproximar mediante una secuencia de cuerpos anidados, hasta llegar a uno de volumen conocido (una hiperesfera). Este enfoque se utiliza para estimar el factor por el cual cambia el volumen en cada paso de esta secuencia. Al multiplicar estos factores se obtiene el volumen aproximado del cuerpo original.

Esta obra le valió a sus autores el Premio Fulkerson en 1991. ^[5]

Mejoras

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

Generalizaciones

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. ^[10] Esto se relaciona con el problema de medida de Klee .

Referencias

1. Elekes, G. (1986), "Una desigualdad geométrica y la complejidad del cálculo del volumen", Geometría discreta y computacional , 1 (4): 289–292, doi : 10.1007/BF02187701 , MR  0866364
2. Bárány, Imre ; Füredi, Zoltán (1987), "Calcular el volumen es difícil", Geometría computacional y discreta , 2 (4): 319–326, doi : 10.1007/BF02187886 , hdl : 1813/8572 , MR  0911186
3. Dyer, Martin ; Frieze, Alan (1988), "Sobre la complejidad de calcular el volumen de un poliedro", SIAM Journal on Computing , 17 (5): 967–974, doi :10.1137/0217060, MR  0961051
4. Dyer, Martin ; Frieze, Alan ; Kannan, Ravi (1991), "Un algoritmo aleatorio de tiempo polinomial para aproximar el volumen de cuerpos convexos", Journal of the ACM , 38 (1): 1–17, doi : 10.1145/102782.102783 , MR  1095916, S2CID  13268711
5. Ganadores del Premio Fulkerson, American Mathematical Society , consultado el 3 de agosto de 2017.
6. Applegate, David ; Kannan, Ravi (1991), "Muestreo e integración de funciones casi logarítmicas cóncavas", Actas del vigésimo tercer simposio anual de la ACM sobre teoría de la computación (STOC '91) , Nueva York, NY, EE. UU.: ACM, págs. 156-163, doi : 10.1145/103418.103439 , ISBN 978-0-89791-397-3, Número de identificación del sujeto  15432190
7. Kannan, Ravi ; Lovász, László ; Simonovits, Miklós (1997), "Paseos aleatorios y un algoritmo de volumen para cuerpos convexos", Random Structures & Algorithms , 11 (1): 1–50, doi :10.1002/(SICI)1098-2418(199708)11:1< 1::AID-RSA1>3.0.CO;2-X, SEÑOR  1608200 ${\displaystyle O^{*}(n^{5})}$
8. Lovász, L. ; Simonovits, M. (1993), "Paseos aleatorios en un cuerpo convexo y un algoritmo de volumen mejorado", Random Structures & Algorithms , 4 (4): 359–412, doi :10.1002/rsa.3240040402, MR  1238906
9. Lovász, L. ; Vempala, Santosh (2006), "Recocido simulado en cuerpos convexos y un algoritmo de volumen", Journal of Computer and System Sciences , 72 (2): 392–417, doi : 10.1016/j.jcss.2005.08.004 , MR  2205290 ${\displaystyle O^{*}(n^{4})}$
10. Bringmann, Karl; Friedrich, Tobias (1 de agosto de 2010). "Aproximación del volumen de uniones e intersecciones de objetos geométricos de alta dimensión". Geometría computacional . 43 (6): 601–610. arXiv : 0809.0835 . doi :10.1016/j.comgeo.2010.03.004. hdl :11858/00-001M-0000-000F-1603-4. ISSN  0925-7721. S2CID  5930593.