Nuevos y mejores algoritmos para el problema de la secretaria en matroides
Professor Advisor
dc.contributor.advisor
Soto San Martín, José
Author
dc.contributor.author
Turkieltaub Melo, Abner
Associate professor
dc.contributor.other
Correa Haeussler, José
Associate professor
dc.contributor.other
Kiwi Krauskopf, Marcos
Admission date
dc.date.accessioned
2017-10-11T17:07:27Z
Available date
dc.date.available
2017-10-11T17:07:27Z
Publication date
dc.date.issued
2017
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/145179
General note
dc.description
Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas.
Ingeniero Civil Matemático
es_ES
Abstract
dc.description.abstract
Estudiamos una generalización del problema de la secretaria llamada el problema matroidal de la secretaria propuesta en 2007 por Babaioff et al. [1]. En este problema, los elementos de una matroide se revelan en orden aleatorio. Al observar un elemento, debemos decidir de forma irrevocable si incluirlo o no en nuestra solución. Los elementos aceptados deben formar un conjunto independiente y deseamos que sea cercano al independiente óptimo. En su trabajo, Babaioff et al. [1] conjeturaron la existencia de un algoritmo O(1)-competitivo para este problema en cualquier matroide. Dicha conjetura sigue abierta, y solo se ha podido probar en clases particulares de matroides.
Por un lado esta tesis sirve como lectura introductoria al problema ya que incluye una
introducción a lo que son las matroides y al problema de la secretaria. Por otro lado presentamos nuevos resultados sobre este problema. Desarrollamos una nueva técnica para diseñar y analizar algoritmos con la cual obtenemos nuevos algoritmos O(1)-competitivos para cuatro clases de matroides: transversales, gráficas, laminares y un tipo especial de matroides representables que llamaremos k-sparsas. En todos estos casos, nuestros algoritmos funcionan aún bajo hipótesis más restrictivas que las del problema original, y logran una mejor competitividad que la de los mejores algoritmos publicados para esos problemas. Además planteamos y estudiamos algunas variantes del problema.
es_ES
Patrocinador
dc.description.sponsorship
Este trabajo ha sido parcialmente financiado por Fondecyt de Iniciación 11130266: APPROXIMATIONALGORITHMS FOR INCREMENTAL SELECTION PROBLEMS