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

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
نویسندگان
, , ,