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 language | English |
|---|---|
| Pages (from-to) | 323-325 |
| Number of pages | 3 |
| Journal | Information Processing Letters |
| Volume | 111 |
| Issue number | 7 |
| DOIs | |
| Publication status | Published - Mar 1 2011 |
| Externally published | Yes |
Fingerprint
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 journal › Article
}
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 -