TY - JOUR
T1 - Maximum subset intersection
AU - Clifford, Raphaël
AU - Popa, Alexandru
N1 - Funding Information:
The authors would like to thank Andrew Moss for introducing us to the problem. We would also like to thank to Anna Adamaszek for pointing us to the open problem discussed at the end and Bogdan Warinschi for helpful comments on an earlier draft of the paper. The second author is funded by an EPSRC PhD studentship.
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
AN - SCOPUS:78650566209
VL - 111
SP - 323
EP - 325
JO - Information Processing Letters
JF - Information Processing Letters
SN - 0020-0190
IS - 7
ER -