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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$L' \subseteq L$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>L</mi> <mo>′</mo> </msup> <mo>⊆</mo> <mi>L</mi> </mrow> </math></EquationSource> </InlineEquation> with <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$|L'| = k$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mrow> <mo stretchy="false">|</mo> </mrow> <msup> <mi>L</mi> <mo>′</mo> </msup> <mrow> <mo stretchy="false">|</mo> <mo>=</mo> <mi>k</mi> </mrow> </mrow> </math></EquationSource> </InlineEquation> such that the intersection of the subsets in <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$L'$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>L</mi> <mo>′</mo> </msup> </math></EquationSource> </InlineEquation> is maximized. This problem is <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathcal{N}\mathcal{P}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">N</mi> <mi mathvariant="script">P</mi> </mrow> </math></EquationSource> </InlineEquation>-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 <Emphasis FontCategory="NonProportional">swap(1,1)</Emphasis> neighborhood structure. To enhance efficiency, we introduce an auxiliary data structure which precomputes partial intersections, reducing the complexity of evaluating a neighboring solution from <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$O(k^2)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> 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.

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

期刊论文
发表日期：

2025年9月28日

查看全文

Hélder Silva Ferreira,
Rian G. S. Pinheiro

摘要

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^{'} \subseteq 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.

An iterated local search heuristic for the maximum Intersection of \(k\)-subsets problem

摘要