Procedimentos de Redução para o Problema da Máxima Interseção de k-Subconjuntos

Vol 54, 2022 - 152650
Trabalho completo (oral)
Favoritar este trabalho
Como citar esse trabalho?
Resumo

O Problema da Máxima Interseção de $k$-Subconjunto é definido como: dado uma coleção $\mathcal{S}$ de subconjuntos do conjunto finito $B$ e um inteiro $k$, deseja-se selecionar $k$ subconjuntos $S_1, S_2, \ldots, S_k \in \mathcal{S}$, tal que $|S_1 \cap \ldots \cap S_k|$ seja máxima. Na literatura, existem procedimentos de redução que visam remover vértices do grafo de entrada que não estarão em uma solução ótima de custo maior ou igual a uma solução viável conhecida. Neste trabalho, apresentamos um novo procedimento de redução e uma estratégia de redução que pode ser combinada com os procedimentos já existentes na literatura. Realizamos exaustivos experimentos computacionais para encontrar o melhor procedimento de redução. Os resultados dos testes computacionais mostram que a estratégia de redução combinada com procedimento de redução menos efetivo supera o melhor procedimento de redução.

Compartilhe suas ideias ou dúvidas com os autores!

Sabia que o maior estímulo no desenvolvimento científico e cultural é a curiosidade? Deixe seus questionamentos ou sugestões para o autor!

Faça login para interagir

Tem uma dúvida ou sugestão? Compartilhe seu feedback com os autores!

Instituições
  • 1 Universidade Federal do Ceará
  • 2 UNIVERSIDADE FEDERAL DO CEARÁ
Eixo Temático
  • 14 - OC – Otimização Combinatória
Palavras-chave
Problema da Máxima Interseção de k-Subconjuntos
Procedimento de redução
Contração de vértice