Maximum subset intersection

Raphaël Clifford, Alexandru Popa

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)


Consider the following problem. Given u sets of sets A1, ⋯,Au with elements over a universe E={e1,⋯, en}, the goal is to select exactly one set from each of A 1,⋯,Au in order to maximize the size of the intersection of the sets. In this paper we present a gap-preserving reduction from Max-Clique which enables us to show that our problem cannot be approximated within an n1-ε multiplicative factor, for any ε>0, unless P=NP (Zuckerman, 2006 [12]).

Original languageEnglish
Pages (from-to)323-325
Number of pages3
JournalInformation Processing Letters
Issue number7
Publication statusPublished - Mar 1 2011


  • Approximation algorithms
  • Combinatorial problems

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Maximum subset intersection'. Together they form a unique fingerprint.

Cite this