標題: | On the inapproximability of maximum intersection problems |
作者: | Shieh, Min-Zheng Tsai, Shi-Chun Yang, Ming-Chuan 資訊工程學系 Department of Computer Science |
關鍵字: | Approximation algorithm;Theory of computation;Inapproximability;Maximum intersection;Disclosure control |
公開日期: | 15-十月-2012 |
摘要: | 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. |
URI: | http://dx.doi.org/10.1016/j.ipl.2012.06.014 http://hdl.handle.net/11536/16807 |
ISSN: | 0020-0190 |
DOI: | 10.1016/j.ipl.2012.06.014 |
期刊: | INFORMATION PROCESSING LETTERS |
Volume: | 112 |
Issue: | 19 |
起始頁: | 723 |
結束頁: | 727 |
顯示於類別: | 期刊論文 |