• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Bases optimales en matroides con incertidumbre y cómo encontrarlas con consultas de costo mínimo

Merino Figueroa, Arturo Ignacio January 2018 (has links)
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

Page generated in 0.0824 seconds