On the inapproximability of maximum intersection problems

作     者：Shieh, Min-Zheng Tsai, Shi-Chun Yang, Ming-Chuan 

作者机构：Natl Chiao Tung Univ Dept Comp Sci Hsinchu Taiwan Natl Chiao Tung Univ Informat & Commun Technol Labs Hsinchu Taiwan 

出 版 物：《INFORMATION PROCESSING LETTERS》 (信息处理快报)

年 卷 期：2012年第112卷第19期

页      面：723-727页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Council of Taiwan [NSC-97-2221-E-009-064-MY3  NSC-98-2221-E-009-078-MY3] 

主　　题：Approximation algorithm Theory of computation Inapproximability Maximum intersection Disclosure control 

摘      要：Given a 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 1/2n(1-2 epsilon) + O(n(1-3 epsilon)) unless P = NP. This answers an open question about its hardness. We also give a correct proof of an inapproximable result by Clifford and Papa (2011) [3] by proving that MAX-INTERSECT problem is equivalent to the MAX-CLIQUE problem. (C) 2012 Elsevier B.V. All rights reserved.