El problema de sistemas de representantes sin sesgo geométricos es NP-completo

Ponente(s): Leonardo Ignacio Martínez Sandoval, A. Banik, B. Bhattacharya, S. Bhore

Supongamos que tenemos un tratamiento médico que se quiere probar en cierta población de personas $P=\{1,2,\ldots,n\}$. Esa población está dividida de acuerdo a varias clasificaciones binarias (adulto/niño, sano/enfermo, local/extranjero, peso bajo/peso alto, etc.), representadas por bicoloraciones $B_1,\ldots,B_m$ de $P$. Sería ideal encontrar pocos subconjuntos $S_1,\ldots,S_k$ de $P$ de manera que para cada bicoloración (cada clasificación binaria), se tenga que alguno de $S_1,\ldots,S_k$ tenga la misma cantidad de puntos de un color, que del otro. Por ejemplo, si bastara un subconjunto $S_1$, entonces podríamos hacer la prueba del tratamiento médico en $S_1$, y para todas las clasificaciones binarias tendríamos una representación balanceada de cada clase. Encontrar dicho mínimo se le conoce como el problema del sistema de representantes sin sesgo mínimo. En esta plática hablamos de una variante geométrica de este problema, donde $P$ son elementos de un espacio Euclideano (que representa, digamos, ubicaciones geográficas) y $S_1,\ldots,S_k$ sólo podemos obtenerlos de rangos geométricos como cajas o discos. Veremos que incluso variantes sencillas de este problema son NP-completas.