Abordagens Heurísticas e Exatas para o Problema da Máxima Interseção de k-Subconjuntos

Abstract

The Maximum k-Subset Intersection Problem can be defined as follows: given two sets L and R, where L = {S1,S2,··· ,Sp} is a collection of p subsets of R = {e1, e2,··· , eq}, and a positive integer k, we have to find k subsets belonging to L such that their intersection is maximum. This problem has already been shown to belong to the class N P-hard and has applications in the area of data privacy and social networks. The objective of this work was to propose new approaches, exact and heuristic, for the Maximum k-Subset Intersection Problem. In this work, we propose two greedy heuristics, two Metaheuristics algorithms, a Branch and Bound algorithm and a formulation of Integer Linear Programming. In addition, a new Reduction Test procedure has been proposed, which aims to reduce the scale of the problem. Random instances were generated and several computational tests were performed. The computational results showed that the proposed Metaheuristic algorithms surpass the state-of-the-art heuristic algorithm in solution quality or in execution time. Regarding the exact approaches, the proposed Branch and Bound algorithm proved to be more efficient than the state-of-the-art method for instances where the graph has a low or medium density.