A note on a maximum k-subset intersection problem

Consider the following problem which we call Maximum k-Subset Intersection (MSI): Given a col-lection C = {S1,..., Sm} of m subsets over a finite set of elements E = {e1,..., en}, and a positive integer k, the objective is to select exactly k subsets Sj1,..., Sjk whose intersection size |Sj1 ∩... ∩ Sjk | is maximum. In [2], Clifford and Popa studied a related problem and left as an open problem the status of the MSI problem. In this paper we show that this problem is hard to approximate