Um Algoritmo VNS para o Problema da Máxima Interseção de k Subconjuntos

Neste trabalho, estudamos o problema da máxima interseção de $k$-subconjuntos (\KMIS). Dado um grafo bipartido $G(L \cup R, E)$, sendo $R$ é o conjunto dos elementos, $L$ o conjunto dos subconjuntos de $R$, e um inteiro $k$, o problema (\KMIS) consiste em encontrar um subconjunto $L' \subseteq L$ com $|L'| = k$ tal que $\cap(L')$ seja máxima, sendo $\cap(L') = |\cap_{C \in L'} C|$. Este problema possui aplicações importantes como, por exemplo, no controle de privacidade de dados de pacientes em hospitais. O algoritmo do estado da arte para o problema é o algoritmo Grasp Reativo apresentado em \cite{bogue:14}. Neste trabalho,
desenvolvemos duas heurísticas gulosas e um algoritmo de busca em vizinhança variável (VNS), com a busca local Descida em Vizinhança Variável (VND) e um algoritmo de segunda ordem para guiar a fase de agitação. Resultados computacionais mostraram que o novo algoritmo supera o algoritmo do estado da arte.