On the inapproximability of maximum intersection problems

檔案

日期

2012-10-15

期刊名稱

INFORMATION PROCESSING LETTERS

摘要

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.

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

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

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/16807