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

Favorite this paper
How to cite this paper?
Details
  • Presentation type: Trabalho completo (oral)
  • Track: 14. OC – Otimização Combinatória
  • Keywords: 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Á

Abstract

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.

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!