En el análisis de algoritmos , varios autores han estudiado el cálculo del volumen de cuerpos convexos de alta dimensión , problema que también se puede utilizar para modelar muchos otros problemas de enumeración combinatoria . A menudo, estos trabajos utilizan un modelo de cálculo de caja negra en el que la entrada viene dada por una subrutina para probar 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-duro . [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 encontrar un aproximación al volumen de un cuerpo convexo en -espacio euclidiano dimensional asumiendo 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:
- Mediante el uso de un método de Monte Carlo de cadena de Markov (MCMC), es posible generar puntos que están distribuidos aleatoriamente de manera casi uniforme dentro de un cuerpo convexo dado. El esquema básico del algoritmo es un muestreo casi uniforme desde dentro colocando una cuadrícula que consta de -cubos dimensionales y hacer una caminata aleatoria sobre estos cubos. Al utilizar la teoría de la mezcla rápida de cadenas de Markov , muestran que se necesita un tiempo polinomial para que el recorrido aleatorio se establezca en una distribución casi uniforme. [4]
- Al utilizar el muestreo de 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 factor pequeño el uno del otro. 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, llegando finalmente a uno de volumen conocido (una hiperesfera), con este enfoque utilizado para estimar el factor por el cual el volumen cambia en cada paso de esta secuencia. Al multiplicar estos factores, se obtiene el volumen aproximado del cuerpo original.
Este trabajo le valió a sus autores el Premio Fulkerson de 1991 . [5]
Mejoras
Aunque el tiempo de este algoritmo es polinomial, tiene un exponente alto. Los 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]
Generalizaciones
El resultado de la aproximabilidad de tiempo polinómico 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
- ^ Elekes, G. (1986), "Una desigualdad geométrica y la complejidad del volumen de cálculo", Geometría discreta y computacional , 1 (4): 289-292, doi : 10.1007 / BF02187701 , MR 0866364
- ^ Bárány, Imre ; Füredi, Zoltán (1987), "Calcular el volumen es difícil", Geometría discreta y computacional , 2 (4): 319–326, doi : 10.1007 / BF02187886 , MR 0911186
- ^ 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
- ^ a b Dyer, Martin ; Frieze, Alan ; Kannan, Ravi (1991), "Un algoritmo de tiempo polinómico aleatorio para aproximar el volumen de cuerpos convexos", Journal of the ACM , 38 (1): 1-17, doi : 10.1145 / 102782.102783 , MR 1095916 , S2CID 13268711
- ^ Ganadores del premio Fulkerson , American Mathematical Society , consultado el 3 de agosto de 2017.
- ^ Applegate, David ; Kannan, Ravi (1991), "Muestreo e integración de funciones casi logarítmicas cóncavas", Actas del vigésimo tercer Simposio Anual de 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, S2CID 15432190
- ^ Kannan, Ravi ; Lovász, László ; Simonovits, Miklós (1997), "Paseos aleatorios y unalgoritmo de volumen para cuerpos convexos ", Estructuras y algoritmos aleatorios , 11 (1): 1–50, doi : 10.1002 / (SICI) 1098-2418 (199708) 11: 1 <1 :: AID-RSA1> 3.0.CO; 2 -X , MR 1608200
- ^ Lovász, L .; Simonovits, M. (1993), "Caminatas al azar en un cuerpo convexo y un algoritmo de volumen mejorado", Estructuras y algoritmos aleatorios , 4 (4): 359–412, doi : 10.1002 / rsa.3240040402 , MR 1238906
- ^ Lovász, L .; Vempala, Santosh (2006), "Recocido simulado en cuerpos convexos y unaalgoritmo de volumen ", Journal of Computer and System Sciences , 72 (2): 392–417, doi : 10.1016 / j.jcss.2005.08.004 , MR 2205290
- ^ 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 . ISSN 0925-7721 . S2CID 5930593 .