On the inapproximability of maximum intersection problems
摘要
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.
關鍵詞
Approximation algorithmTheory of computationInapproximabilityMaximum intersectionDisclosure control所屬典藏
期刊論文引用此條目
Shieh, M.-Z., Tsai, S.-C., & Yang, M.-C. (2012). On the inapproximability of maximum intersection problems. INFORMATION PROCESSING LETTERS, 112(19), 723–727. https://doi.org/10.1016/j.ipl.2012.06.014
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/16807