A note on a Maximum k-Subset Intersection problem

详细信息	查看全文 | 推荐本文 |

• 作者：Eduardo C. Xavier¹ ; ^{eduardo@ic.unicamp.br}
• 关键词：Approximation algorithms ; Combinatorial problems ; Subset intersection
• 刊名：Information Processing Letters
• 出版年：2012
• 期刊代码：61_00200190
• 类别：cp
• 出版时间：30 June, 2012
• 卷：112
• 期：12
• 页码：471-472
• 文件大小：105 K

摘要

Consider the following problem which we call Maximum k-Subset Intersection (MSI): Given a collection of m subsets over a finite set of elements , and a positive integer k, the objective is to select exactly k subsets whose intersection size is maximum. In , 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.