A note on a Maximum k-Subset Intersection problem

作者：Xavier Eduardo C^*

来源：Information Processing Letters, 2012, 112(12): 471-472.

DOI：10.1016/j.ipl.2012.03.007

• Approximation algorithms
• Combinatorial problems
• Subset intersection

Consider the following problem which we call Maximum k-Subset Intersection (MSI): Given a collection C = {S-1 . . . . . S-m} of m subsets over a finite set of elements epsilon = {e(1) . . . . . e(n)}(,) and a positive integer k, the objective is to select exactly k subsets S-j1 . . . . .S-jk whose intersection size vertical bar S-j1 boolean AND . . . boolean AND S-jk vertical bar is maximum. In [2], Clifford and Popa (2011) 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.

• 出版日期2012-6-30