On the inapproximability of maximum intersection problems
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
727 | en_US |
dc.citation.issue |
19 | en_US |
dc.citation.spage |
723 | en_US |
dc.citation.volume |
112 | en_US |
dc.citation.woscount |
0 | |
dc.contributor.author |
Shieh, Min-Zheng | en_US |
dc.contributor.author |
Tsai, Shi-Chun | en_US |
dc.contributor.author |
Yang, Ming-Chuan | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:24:09Z | |
dc.date.available |
2014-12-08T15:24:09Z | |
dc.date.issued |
2012-10-15 | en_US |
dc.description.abstract |
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. | en_US |
dc.identifier.doi |
10.1016/j.ipl.2012.06.014 | en_US |
dc.identifier.issn |
0020-0190 | en_US |
dc.identifier.journal |
INFORMATION PROCESSING LETTERS | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.ipl.2012.06.014 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/16807 | |
dc.identifier.wosnumber |
WOS:000307681900004 | |
dc.language.iso |
en_US | en_US |
dc.subject |
Approximation algorithm | en_US |
dc.subject |
Theory of computation | en_US |
dc.subject |
Inapproximability | en_US |
dc.subject |
Maximum intersection | en_US |
dc.subject |
Disclosure control | en_US |
dc.title |
On the inapproximability of maximum intersection problems | en_US |
dc.type |
Article | en_US |
檔案
- 000307681900004.pdf (168.5 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
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