Maximum subset intersection

R Clifford; A Popa

doi:10.1016/j.ipl.2010.12.003

Maximum subset intersection

R Clifford
, A Popa

Research output: Contribution to journal › Article (Academic Journal) › peer-review

16 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 contribution	Maximum subset intersection
Original language	English
Pages (from-to)	323 - 325
Number of pages	3
Journal	Information Processing Letters
Volume	111
DOIs	https://doi.org/10.1016/j.ipl.2010.12.003
Publication status	Published - Mar 2011

Bibliographical note

Publisher: Elsevier

Access to Document

10.1016/j.ipl.2010.12.003

Handle.net

Persistent link

Cite this

@article{d3811ba8b3c54fbb90ffa4116747cadc,

title = "Maximum subset intersection",

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\textasciicircum{}(1−epsilon) multiplicative factor, for any epsilon >0, unless P=NP.",

author = "R Clifford and A Popa",

note = "Publisher: Elsevier",

year = "2011",

month = mar,

doi = "10.1016/j.ipl.2010.12.003",

language = "English",

volume = "111",

pages = "323 -- 325",

journal = "Information Processing Letters",

issn = "1872-6119",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Maximum subset intersection

AU - Clifford, R

AU - Popa, A

N1 - Publisher: Elsevier

PY - 2011/3

Y1 - 2011/3

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

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

U2 - 10.1016/j.ipl.2010.12.003

DO - 10.1016/j.ipl.2010.12.003

M3 - Article (Academic Journal)

SN - 1872-6119

VL - 111

SP - 323

EP - 325

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Maximum subset intersection

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this