Algorithms for the single-sample prophet-secretary problem for matchings and related systems

Abstract

El problema clásico de la secretaria introdujo una plétora de generalizaciones. En esta tesis se estudia la versión donde tenemos una sola muestra de las distribuciones de cada valor, en el caso particular donde los valores a optimizar son aristas de un emparejamiento en un grafo. Obtenemos un algoritmo 3-competitivo para este problema, y un algoritmo k + 1- competitivo para el caso donde en vez de emparejamientos de un grafo clásico trabajamos con emparejamientos de un hipergrafo donde cada arista tiene tamaño a lo más k. También extendemos estos resultados a sistemas más generales. Se introduce el paradigma de sistemas k-dirigidos: para ciertas clases de matroides, y más generalmente, sistemas de independencia compartiendo una propiedad en particular con problemas de emparejamiento, obtenemos el mismo resultado de aproximación de un algoritmo k + 1-competitivo en el caso de sistemas que admiten una representación k-dirigida.

The classic secretary problem introduced a plethora of generalizations. In this thesis, we study the version where we have a single sample of the distribution of each value, in the particular case where the values to optimize are edges forming a matching in a graph. We obtain a 3-competitive algorithm for this problem, and a k + 1-competitive algorithm for the case where instead of a graph we work with matchings in a hypergraph where each edge has size at most k. We also extend this results to more general problems, introducing the paradigm of k-directed systems. For certain classes of matroids, and more generally, independence system sharing a particular property with matching problems, we obtain the same approximation result of a k + 1-competitive algorithm in the case that the system admits a k-directed representation.