On the inapproximability of maximum intersection problems

Given u sets, we want to choose exactly k sets such that the cardinality of their intersection is maximized. This is the so-called MAX-k-INTERSECT problem. We prove that MAX-k  -INTERSECT cannot be approximated within an absolute error of 12n1−2ϵ+O(n1−3ϵ) unless P=NPP=NP. This answers an open question about its hardness. We also give a correct proof of an inapproximable result by Clifford and Popa (2011) [3] by proving that MAX-INTERSECT problem is equivalent to the MAX-CLIQUE problem.

► We study the hardness of two maximum intersection problems. ► We prove that MAX-INTERSECT problem is equivalent to the MAX-CLIQUE problem. ► We prove that MAX-k  -INTERSECT problem cannot be approximated within an absolute error factor unless P=NPP=NP.