Multiple Matroid Secretary Problem : nuevos enfoques del problema clásico

Abstract

En este documento definimos y estudiamos una generalización del \textit{Matroid Secretrary Problem} (MSP), que denominamos \textit{Multiple Matroid Secretary Problem}. En el MSP, los elementos de una matroide se revelan uno a uno y en orden alearorio, de manera que al observar un elemento y su peso, se debe decidir de manera irrevocable si se agrega o no al conjunto solución, bajo la condición que este último sea un conjunto independiente para la matroide en cuestión. El objetivo es devolver el conjunto independiente de peso máximo. En nuestra generalización, relajamos la condición de que cada elemento que se introduzca al conjunto solución mantenga la condición de independencia, en cambio, permitimos la construcción $J$ conjuntos independientes, de forma que podemos incluir elementos de la matroide siempre que mantengan esta independencia en alguno de los $J$ conjuntos.\\

Si bien el problema definido en esta tesis es más sencillo que problema original, no es claro cómo extender los algoritmos de un contexto a otro, ni cómo se relacionan las competitividades de ambos problemas. Una de las razones por las cuales este problema es interesante, radica en que puede abrir paso a nuevos enfoques para lograr responder la conjetura de Babaioff et al. \cite{Babaioff07} y que, por otro lado, nos muestra otras perspectivas en las diferentes clases de matroides donde ya se conocen algoritmos que alcanzan competitividad constante, por ejemplo entendiendo el comportamiento asintótico de sus competitividades a medida que la cantidad de independientes $J$ aumenta. Nuestro conjunto solución a devolver será $\OPT(F_1 \cup \dots \cup F_J)$.\\

Realizamos un completo repaso por el estado del arte y los diferentes problemas de secretario y las pertinentes definiciones y estudiamos este nuevo problema en matroides uniformes, transversales, gráficas y todas aquellas que admitan certificadores $k$-dirigidos. Al final de esta tesis, también exponemos un capítulo dedicado al estudio de matroides con cintura ancha.\\

Para el caso de la clase de matroides trasversales, si bien se sabe que la matroide transversal es ``bien comportada'' para el \emph{Matroid Secretary Problem} —en el sentido de que se optimiza en \( p=1/e \), al igual que el problema clásico, y alcanza la misma competitividad—, en esta tesis probamos que para el nuevo problema \emph{Multiple-Matroid Secretary Problem} sucede exactamente lo mismo. Este nuevo problema hereda todas las propiedades favorables del problema clásico. Incluso al considerar más de un independiente, somos capaces de construir un algoritmo para el $J$-MSP en la matroide transversal que se optimizan en los mismos parámetros definidos para el algoritmo óptimo del \((J,1)\)-SP y obtenemos las mismas competitividades. De esta manera, caracterizamos completamente la matroide transversal.