Maximum subset intersection

Raphaël Clifford, Alexandru Popa

Research output: Contribution to journalArticle

11 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
Externally publishedYes

Fingerprint

Intersection
Subset
Clique
Multiplicative
Maximise

Keywords

  • Approximation algorithms
  • Combinatorial problems

ASJC Scopus subject areas

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

Cite this

Maximum subset intersection. / Clifford, Raphaël; Popa, Alexandru.

In: Information Processing Letters, Vol. 111, No. 7, 01.03.2011, p. 323-325.

Research output: Contribution to journalArticle

Clifford, Raphaël ; Popa, Alexandru. / Maximum subset intersection. In: Information Processing Letters. 2011 ; Vol. 111, No. 7. pp. 323-325.
@article{0990422e1fad4b8a8d7cc362128ad145,
title = "Maximum subset intersection",
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]).",
keywords = "Approximation algorithms, Combinatorial problems",
author = "Rapha{\"e}l Clifford and Alexandru Popa",
year = "2011",
month = "3",
day = "1",
doi = "10.1016/j.ipl.2010.12.003",
language = "English",
volume = "111",
pages = "323--325",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "7",

}

TY - JOUR

T1 - Maximum subset intersection

AU - Clifford, Raphaël

AU - Popa, Alexandru

PY - 2011/3/1

Y1 - 2011/3/1

N2 - 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]).

AB - 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]).

KW - Approximation algorithms

KW - Combinatorial problems

UR - http://www.scopus.com/inward/record.url?scp=78650566209&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78650566209&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2010.12.003

DO - 10.1016/j.ipl.2010.12.003

M3 - Article

VL - 111

SP - 323

EP - 325

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 7

ER -