Maximum subset intersection

Raphaël Clifford, Alexandru Popa

Research output: Contribution to journalArticle

12 Citations (Scopus)

Abstract

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
Volume111
Issue number7
DOIs
Publication statusPublished - Mar 1 2011

    Fingerprint

Keywords

  • Approximation algorithms
  • Combinatorial problems

ASJC Scopus subject areas

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

Cite this