On the inapproximability of maximum intersection problems

Min-Zheng Shieh, Shi-Chun Tsai*, Ming Chuan Yang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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 1/2n 1-2ε+O(n 1-3ε) unless P=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.

Original languageEnglish
Pages (from-to)723-727
Number of pages5
JournalInformation Processing Letters
Volume112
Issue number19
DOIs
StatePublished - 15 Oct 2012

Keywords

  • Approximation algorithm
  • Disclosure control
  • Inapproximability
  • Maximum intersection
  • Theory of computation

Fingerprint Dive into the research topics of 'On the inapproximability of maximum intersection problems'. Together they form a unique fingerprint.

Cite this