Algoritmos para problemas de optimización bajo total monotonía

Résumé

En esta memoria se desarrollan algoritmos on-line para buscar mínimos en matrices multidimensionales bajo la propiedad de total monotonia, Este tipo de cuestiones aparecen de una forma natural al formular problemas de recorridos en el plano utilizando las técnicas de programación dinámica. En primer lugar, se diseña un algoritmo lineal de busqueda de mínimos en mátrices monge path-de composable tridimensionales. Este algoritmo permite resolver de forma óptima tres problemas de optimización bien conocidos en la literatura: el problema de la curva kamiltoniana de longitud unina con extremos fijos en un onvexo. El problema del viajante de comercio para puntos sobre un convexo y una recta en su interior, y el problema de mínima latencia en grafos camino. A continuación, el algoritmo dado se generaliza para búsqueda on-line de mínimos en matrices monge path-recompensable de mayor dimensión. Además, diseñamos un algoritmo on-line para matrices multidimensionales que satisfacen la propiedad monge en lugar de la monge path-decomposable. Por otra parte, para matrices antimonge path-decomposable tridimensionales damos un algoritmo de complejidad O(NlogN) en tiempo 1 lineal en espacio . Este algoritmo permite resolver de manera más efecientemente que la conocida el problema de la curva hamiltoniana mínima con extremos arbitrarios, tanto en un poligono convexo como en uno simple. Finalmente, damos un algoritmo óptimo para el problema del viajante de comercio con deaolines en un grafio camino.