Maximum subset intersection

R Clifford, A Popa

Research output: Contribution to journalArticle (Academic Journal)

12 Citations (Scopus)

Abstract

Consider the following problem. Given u sets of sets A1,…,Au with elements over a universe, the goal is to select exactly one set from each of A1,…,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 n^(1−epsilon) multiplicative factor, for any epsilon >0, unless P=NP.
Translated title of the contributionMaximum subset intersection
Original languageEnglish
Pages (from-to)323 - 325
Number of pages3
JournalInformation Processing Letters
Volume111
DOIs
Publication statusPublished - Mar 2011

Bibliographical note

Publisher: Elsevier

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

Cite this