Eficiencia y estructuras dinámicas, puntos pareto enteros

Abstract

" El problema que planteamos en nuestro trabajo es la búsqueda de los puntos eficientes enteros de un poliedro, aplicando una generalización de los métodos de enumeración implícita y usando estructuras dinámicas. Dichos métodos enumerativos son desarrollados para ser aplicados a problemas lineales aunque no sean del tipo cero-uno, y la enumeración implícita se hace sobre un entorno de la superficie eficiente del poliedro.Las obtención de los puntos eficientes, exige disponer de estructuras dinámicas de datos adecuadas, que filtren dichos puntos de entre los enumerados, para que en cada momento, el espacio requerido sea mínimo. Las dificultades que aparecen en el proceso, aparte del manejo de las estructuras de datos, es que no sabemos si el conjunto de puntos de coordenadas enteras, pertenecientes al poliedro, es no vacío, y si así fuese, tampoco sabemos la frecuencia con que aparecen dichos puntos. En algunos casos, que llamaremos poliedros denso enteros, se demuestra que puede pasarse de un punto a otro por un camino interior al poliedro, pero en los casos que pueda plantearse la duda de que los puntos enteros estén aislados o no existan, habrá que estudiar nuevos procedimientos y demostrar que con ellos, la accesibilidad a cualquier punto eficiente de coordenadas enteras está garantizada. En el Capítulo 1, hacemos una revisión de las estructuras dinámicas de datos que han sido utilizados en otros problemas de búsqueda multidimensional, fundamentalmente, listas lineales, árboles ordenados, q-árboles y kd-árboles. En el Capítulo 2, aplicamos la estructuras anteriores a la localización de puntos eficientes, y se ha ce un estudio del rendimiento de cada una de ellas obteniéndose el kd-árbol como la estructuras más eficiente en nuestro problemas. En el Capítulo3, demostramos que para los poliedros densos enteros, podemos partir de cualqu|