Tesis para optar al grado de Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas / Memoria para optar al título de Ingeniero Civil Matemático / Estudiamos el problema de bases de peso mínimo en matroides en un contexto donde los pesos en los elementos son inciertos. Inicialmente, para cada elemento $e$ de una matroide $(E,\I)$ se conocerá un conjunto no vacío $A_e \subseteq \mathbb R$, llamado área de incertidumbre, que contiene los posibles pesos del elemento $e$. El algoritmo puede escoger un conjunto de elementos $X\subseteq E$ a consultar, de manera que si un elemento $e$ es consultado se obtiene un peso $w_e \in A_e$ con un costo de consulta $c_e \in \mathbb R$ asociado. El objetivo es encontrar un conjunto $X \subseteq E$ que, al consultarlo, permita calcular una base de peso mínimo independiente del valor de las aristas no reveladas. A estos conjuntos se les llamará consultas factible; tenemos particular interés en encontrar una de costo mínimo. Esto es de especial interés en aplicaciones donde obtener datos exactos es díficil o costoso, pero datos vagos son de fácil acceso.
El problema adaptativo bajo análisis competitivo fue estudiado anteriormente. En este trabajo consideramos el caso no adaptativo; es decir, cuando los elementos a consultar se eligen todos al mismo tiempo. Formalizamos el problema, definimos las bases de peso mínimo en el contexto incierto, caracterizamos su existencia y demostramos que son las bases de una matroide. Proveemos una caracterización de las consultas factibles de tamaño mínimo, probamos que los complementos de consultas factibles forman una matroide sencilla y esto nos permite idear un algoritmo que encuentra una consulta factible de costo mínimo con una cantidad polinomial tanto de recursos computacionales como de llamadas al oráculo de independencia de la matroide / FONDECYT Regular N° 1181180 y CMM - Conicyt PIA AFB170001
| Identifer | oai:union.ndltd.org:UCHILE/oai:repositorio.uchile.cl:2250/168154 |
| Date | January 2018 |
| Creators | Merino Figueroa, Arturo Ignacio |
| Contributors | Soto San Martín, José, Matamala Vásquez, Martín, Rapaport Zimermann, Iván |
| Publisher | Universidad de Chile |
| Source Sets | Universidad de Chile |
| Language | English |
| Detected Language | Spanish |
| Type | Tesis |
| Rights | Attribution-NonCommercial-NoDerivs 3.0 Chile, http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ |
Page generated in 0.0024 seconds