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

Abstract

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