An iterated local search heuristic for the maximum Intersection of $$k$$ k -subsets problem

Hélder Silva Ferreira () and Rian G. S. Pinheiro ()
Additional contact information
Hélder Silva Ferreira: Universidade Federal de Alagoas
Rian G. S. Pinheiro: Universidade Federal de Alagoas

Journal of Heuristics, 2025, vol. 31, issue 4, No 2, 29 pages

Abstract: Abstract Given a collection L of n subsets of a finite set R, the Maximum Intersection of k-Subsets problem (kMIS) aims to select a subset $$L' \subseteq L$$ L ′ ⊆ L with $$|L'| = k$$ | L ′ | = k such that the intersection of the subsets in $$L'$$ L ′ is maximized. This problem is $$\mathcal{N}\mathcal{P}$$ N P -hard and has applications in data anonymization, bioinformatics, recommendation systems, and various other fields. In this work, we propose an Iterated Local Search (ILS) algorithm for solving the kMIS. The local search phase uses the swap(1,1) neighborhood structure. To enhance efficiency, we introduce an auxiliary data structure which precomputes partial intersections, reducing the complexity of evaluating a neighboring solution from $$O(k^2)$$ O ( k 2 ) to O(k). The proposed ILS was evaluated against two state-of-the-art metaheuristics from the literature on 238 benchmark instances. The experimental results demonstrate that our approach efficiently finds high-quality solutions, establishing its competitiveness for solving the kMIS.

Keywords: Combinatorial Optimization; $$k$$ k -Subsets problem; Iterated Local Search; Metaheuristics (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09569-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:4:d:10.1007_s10732-025-09569-y

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09569-y

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().