標題: 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-Oct-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
Appears in Collections:Articles


Files in This Item:

  1. 000307681900004.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.