This paper was published through Galoá and has a deposited DOI. To cite this paper, use one of the standards below:
In case you are one of the co-authors and want to register this paper in your Lattes, use the following code: doi > 10.59254/sbpo-2020-122671
If you've NEVER registered a DOI in your Lattes, check our tutorial!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Á
Now you could share with me your questions, observations and congratulations
Create a topicWatch this next:
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.
With nearly 200,000 papers published, Galoá empowers scholars to share and discover cutting-edge research through our streamlined and accessible academic publishing platform.
Learn more about our products:
This proceedings is identified by a DOI , for use in citations or bibliographic references. Attention: this is not a DOI for the paper and as such cannot be used in Lattes to identify a particular work.
Check the link "How to cite" in the paper's page, to see how to properly cite the paper