Reactive VNS algorithm for the maximum k-subset intersection problem
- PDF / 407,722 Bytes
- 29 Pages / 439.37 x 666.142 pts Page_size
- 95 Downloads / 188 Views
Reactive VNS algorithm for the maximum k-subset intersection problem Fabio C. S. Dias1 · Wladimir Araújo Tavares1 · José Robertty de Freitas Costa1 Received: 27 November 2018 / Revised: 7 October 2019 / Accepted: 18 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper proposes a reactive VNS metaheuristic for the maximum intersection of k-subsets problem (kMIS). The kMIS is defined as: Given a set of elements, a subset family of the first set and an integer k. The problem consists of finding k subset so that the intersection is maximum. Our VNS metaheuristic incorporates strategies used in GRASP metaheuristics, such as the GRASP construction phase and the Reactive GRASP. Both were used in the shaking phase as a reactive components to VNS. We also propose what we call teh Dynamic Step, a new way to increase the VNS neighborhood. All of these strategies, as well as the Skewed VNS, were added to our Reactive VNS algorithm for kMIS. Computational results showed that the new algorithm outperforms the state-of-the-art algorithm. Keywords Reactive VNS · Metaheuristics · Heuristics · Maximum intersection of k-subsets problem
1 Introduction The Maximum k-Subset Intersection (kMIS) problem can be defined as follows: Given a collection L of subsets of a set R and an integer k, we have to select L ⊆ L with |L | = k such that | ∩ S∈L S| is maximum. The problem can be modeled as a bipartite graph where the left side vertices represent subsets that are in L and the right side vertices represent the elements of R. There is an edge between an i vertex associated
B
Fabio C. S. Dias [email protected] Wladimir Araújo Tavares [email protected] José Robertty de Freitas Costa [email protected]
1
Campus of Quixadá, Federal University of Ceará, Quixadá, Brazil
123
F. C. S. Dias et al. Fig. 1 Illustration of the bipartite graph construction process from sets L and R described above, with optimal solution highlighted
S1
1 2
S2
3 4
S3
5
with a subset Si ∈ L and a vertex j related to an e j ∈ R if only if e j ∈ Si . For instance, assume R = {1, 2, 3, 4, 5}, L = {S1 , S2 , S3 }, where S1 = {2, 3, 4}, S2 = {1, 4, 5} and S3 = {1, 2, 3, 4}. For k = 2, we have to select the maximum intersection between two subsets. In our example, we have |S1 ∩ S2 | = 1, |S1 ∩ S3 | = 3 and |S2 ∩ S3 | = 2. So the optimal solution is L = {S1 , S3 }. Note that the subgraph induced by the vertices associated with S1 and S3 and the vertices associated with the elements in S1 ∩ S3 defines a complete bipartite graph (Fig. 1). Initially, Vinterbo presented the k-ambiguity problem with information suppression n (Vinterbo 2002). The k-ambiguity problem can be defined as follows: let U = {xi }i=1 be a set of objects of interest. Given an integer k, where much information about an element xi would need to be discarded to makes it indiscernible from other k. This problem naturally occurs in the control of medical data disclosure. In this paper, the kambiguity problem has been shown as equivalent to two
Data Loading...
