کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
429000 | 686994 | 2012 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the inapproximability of maximum intersection problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Given u 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 12n1−2ϵ+O(n1−3ϵ) unless P=NPP=NP. This answers an open question about its hardness. We also give a correct proof of an inapproximable result by Clifford and Popa (2011) [3] by proving that MAX-INTERSECT problem is equivalent to the MAX-CLIQUE problem.
► We study the hardness of two maximum intersection problems.
► We prove that MAX-INTERSECT problem is equivalent to the MAX-CLIQUE problem.
► We prove that MAX-k -INTERSECT problem cannot be approximated within an absolute error factor unless P=NPP=NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 112, Issue 19, 15 October 2012, Pages 723–727
Journal: Information Processing Letters - Volume 112, Issue 19, 15 October 2012, Pages 723–727
نویسندگان
Min-Zheng Shieh, Shi-Chun Tsai, Ming-Chuan Yang,