Um Algoritmo Branch-and-Bound para o Problema da Máxima Interseção de k-Subconjuntos

Favoritar este trabalho
Como citar esse trabalho?
Detalhes
  • Tipo de apresentação: Trabalho completo (oral)
  • Eixo temático: 14. OC – Otimização Combinatória
  • Palavras chaves: Branch-and-bound; Testes de Redução; Problema da Máxima Interseção de k-Subconjuntos;
  • 1 UNIVERSIDADE FEDERAL DO CEARÁ
  • 2 Universidade Federal do Ceará

Um Algoritmo Branch-and-Bound para o Problema da Máxima Interseção de k-Subconjuntos

José Robertty de Freitas Costa

UNIVERSIDADE FEDERAL DO CEARÁ

Resumo

Neste artigo, apresentamos um algoritmo Branch-and-Bound, chamado BBKMIS, para o problema da Máxima Interseção de k-Subconjuntos (KMIS). 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. Para este algoritmo, propomos um procedimento de limite superior, um critério de ramificação e analisamos dois critérios de redução, que podem ser empregados para redução do problema inicial e/ou de cada subproblemas no árvore de Branch-and-Bound. O primeiro procedimento de redução foi proposto por Bogue et al. [2014] e o segundo, proposto neste trabalho, estende o anterior. Nos testes computacionais realizados, o algoritmo proposto supera o algoritmo do estado da arte na maior parte das classes de instâncias avaliadas.

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!